We study the problem of estimating the number of edges in an $ n $-vertex graph, accessed
via the Bipartite Independent Set query model introduced by Beame et al.(ITCS'18). In this …

We introduce a new, remarkably powerful tool to the toolbox of algebraic FPT algorithms,
determinantal sieving. Given a polynomial P (x 1,…, xn) over a field 𝔽 of characteristic 2, on …

Sampling edges from a graph in sublinear time is a fundamental problem and a powerful
subroutine for designing sublinear-time algorithms. Suppose we have access to the vertices …

The Voronoi diagrams technique was introduced by Cabello to compute the diameter of
planar graphs in subquadratic time. We present novel applications of this technique in static …

This thesis addresses several challenges in efficiently processing large datasets and in
privacy-preserving computation. Specifically, in this thesis, we look into the following …

For any fixed t, we present two fine-grained reductions of the problem of approximately
counting the number of t-cliques in a graph to the problem of detecting a t-clique in a graph …

Abstract Diese Arbeit betrachtet parametrisierte Algorithmen für Matching-und
Packungsprobleme, deren Erforschung in der Informatik weit verbreitet ist. In diesen …

In this thesis, we study the design and analysis of algorithms for discovering the structure
and properties of an unknown graph, with applications in two different domains: causal …

In this paper, we focus on Hitting-Set, a fundamental problem in combinatorial optimization,
through the lens of sublinear time algorithms. Given access to the hypergraph through a …