We study the task of estimating the number of edges in a graph, where the access to the
graph is provided via an independent set oracle. Independent set queries draw motivation …

We consider the general problem of learning about a matrix through vector-matrix-vector
queries. These queries provide the value of $\boldsymbol {u}^{\mathrm {T}}\boldsymbol …

In this paper, we design efficient algorithms to approximately count the number of edges of a
given k-hypergraph, and to sample an approximately uniform random edge. The hypergraph …

In this paper we carefully combine Fredman's trick [SICOMP'76] and Matoušek's approach
for dominance product [IPL'91] to obtain powerful results in fine-grained complexity. Under …

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 study the problem of finding a spanning forest in an undirected, $ n $-vertex multi-graph
under two basic query models. One is the Linear query model which are linear …

Suppose the fastest algorithm that we can design for some problem runs in time O (n^ 2).
However, we want to solve the problem on big data inputs, for which quadratic time is …

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 …

We develop a new technique for proving lower bounds in the setting of asymmetric
communication, a model that was introduced in the famous works of Miltersen (STOC'94) …

Majority-SAT (aka MAJ-SAT) is the problem of determining whether an input n-variable
formula in conjunctive normal form (CNF) has at least 2^(n-1) satisfying assignments …