BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
The Collision problem is to decide whether a given list of numbers (x1,…,xn)∈[n]n is 1-to-1 or 2-to-1 when promised one of them is the case. We show an nΩ(1) randomised communication lower bound for the natural two-party version of Collision where Alice holds the first half of the bits of each xi and Bob holds the second half. As an application, we also show a similar lower bound for a weak bit-pigeonhole search problem, which answers a question of Itsykson and Riazanov (CCC 2021).
We show EOPL=PLS∩PPAD. Here the class EOPL consists of all total search problems that reduce to the End-of-Potential-Line problem, which was introduced in the works by Hubacek and Yogev (SICOMP 2020) and Fearnley et al. (JCSS 2020). In particular, our result yields a new simpler proof of the breakthrough collapse CLS=PLS∩PPAD by Fearnley et al. (STOC 2021). We also prove a companion result SOPL=PLS∩PPADS, where SOPL is the class associated with the Sink-of-Potential-Line problem.
We use results from communication complexity, both new and old ones, to prove lower bounds for unambiguous finite automata (UFAs). We show three results. Complement: There is a language L recognised by an n-state UFA such that the complement language L requires NFAs with nΩ~(logn) states. This improves on a lower bound by Raskin. Union: There are languages L1, L2 recognised by n-state UFAs such that the union L1∪L2 requires UFAs with nΩ~(logn) states. Separation: There is a language L such that both L and L are recognised by n-state NFAs but such that L requires UFAs with nΩ(logn) states. This refutes a conjecture by Colcombet.
We survey lower-bound results in complexity theory that have been obtained via newfound interconnections between propositional proof complexity, boolean circuit complexity, and query/communication complexity. We advocate for the theory of total search problems (TFNP) as a unifying language for these connections and discuss how this perspective suggests a whole programme for further research.
We prove two results about randomised query complexity R(f). First, we introduce a "linearised" complexity measure LR and show that it satisfies an inner-optimal composition theorem: R(f∘g)≥Ω(R(f)LR(g)) for all partial f and g, and moreover, LR is the largest possible measure with this property. In particular, LR can be polynomially larger than previous measures that satisfy an inner composition theorem, such as the max-conflict complexity of Gavinsky, Lee, Santha, and Sanyal (ICALP 2019). Our second result addresses a question of Yao (FOCS 1977). He asked if ε-error expected query complexity Rˉε(f) admits a distributional characterisation relative to some hard input distribution. Vereshchagin (TCS 1998) answered this question affirmatively in the bounded-error case. We show that an analogous theorem fails in the small-bias case ε=1/2−o(1).
We show that Cutting Planes (CP) proofs are hard to find: Given an unsatisfiable formula F, 1) It is NP-hard to find a CP refutation of F in time polynomial in the length of the shortest such refutation; and 2)unless Gap-Hitting-Set admits a nontrivial algorithm, one cannot find a tree-like CP refutation of F in time polynomial in the length of the shortest such refutation. The first result extends the recent breakthrough of Atserias and Müller (FOCS 2019) that established an analogous result for Resolution. Our proofs rely on two new lifting theorems: (1) Dag-like lifting for gadgets with many output bits. (2) Tree-like lifting that simulates an r-round protocol with gadgets of query complexity O(logr) independent of input length.
We study the search problem class PPAq defined as a modulo-q analog of the well-known polynomial parity argument class PPA introduced by Papadimitriou '94. Our first result shows that this class can be characterized in terms of PPAp for prime p. Our main result is to establish that an explicit version of a search problem associated to the Chevalley--Warning theorem is complete for PPAp for prime p. This problem is natural in that it does not explicitly involve circuits as part of the input. It is the first such complete problem for PPAp when p≥3. Finally we discuss connections between Chevalley-Warning theorem and the well-studied short integer solution problem and survey the structural properties of PPAq.
The randomized query complexity R(f) of a boolean function f:{0,1}n→{0,1} is famously characterized (via Yao's minimax) by the least number of queries needed to distinguish a distribution D0 over 0-inputs from a distribution D1 over 1-inputs, maximized over all pairs (D0,D1). We ask: Does this task become easier if we allow query access to infinitely many samples from either D0 or D1? We show the answer is no: There exists a hard pair (D0,D1) such that distinguishing D0∞ from D1∞ requires Θ(R(f)) many queries. As an application, we show that for any composed function f∘g we have R(f∘g)≥Ω(fbs(f)R(g)) where fbs denotes fractional block sensitivity.
Suppose we have randomized decision trees for an outer function f and an inner function g. The natural approach for obtaining a randomized decision tree for the composed function (f∘gn)(x1,…,xn)=f(g(x1),…,g(xn)) involves amplifying the success probability of the decision tree for g, so that a union bound can be used to bound the error probability over all the coordinates. The amplification introduces a logarithmic factor cost overhead. We study the question: When is this log factor necessary? We show that when the outer function is parity or majority, the log factor can be necessary, even for models that are more powerful than plain randomized decision trees. Our results are related to, but qualitatively strengthen in various ways, known results about decision trees with noisy inputs.
We use critical block sensitivity, a new complexity measure introduced by Huynh and Nordström (STOC 2012), to study the communication complexity of search problems. To begin, we give a simple new proof of the following central result of Huynh and Nordström: if S is a search problem with critical block sensitivity b, then every randomised two-party protocol solving a certain two-party lift of S requires Ω(b) bits of communication. Besides simplicity, our proof has the advantage of generalising to the multi-party setting. We combine these results with new critical block sensitivity lower bounds for Tseitin and Pebbling search problems to obtain the following applications: (1) Monotone Circuit Depth: We exhibit a monotone n-variable function in NP whose monotone circuits require depth Ω(n/logn); previously, a bound of Ω(n) was known (Raz and Wigderson, JACM 1992). Moreover, we prove a Θ(n) monotone depth bound for a function in monotone P. (2) Proof Complexity: We prove new rank lower bounds as well as obtain the first length--space lower bounds for semi-algebraic proof systems, including Lovász--Schrijver and Lasserre (SOS) systems. In particular, these results extend and simplify the works of Beame et al. (SICOMP 2007) and Huynh and Nordström.
We exhibit an n-node graph whose independent set polytope requires extended formulations of size exponential in Ω(n/logn). Previously, no explicit examples of n-dimensional 0/1-polytopes were known with extension complexity larger than exponential in Θ(n). Our construction is inspired by a relatively little-known connection between extended formulations and (monotone) circuit depth.
This work bridges the gap between distributed and centralised models of computing in the context of sublinear-time graph algorithms. A priori, typical centralised models of computing (e.g., parallel decision trees or centralised local algorithms) seem to be much more powerful than distributed message-passing algorithms: centralised algorithms can directly probe any part of the input, while in distributed algorithms nodes can only communicate with their immediate neighbours. We show that for a large class of graph problems, this extra freedom does not help centralised algorithms at all: for example, efficient stateless deterministic centralised local algorithms can be simulated with efficient distributed message-passing algorithms. In particular, this enables us to transfer existing lower bound results from distributed algorithms to centralised local algorithms.
The Pattern self-Assembly Tile set Synthesis (PATS) problem, which arises in the theory of structured DNA self-assembly, is to determine a set of coloured tiles that, starting from a bordering seed structure, self-assembles to a given rectangular colour pattern. The task of finding minimum-size tile sets is known to be NP-hard. We explore several complete and incomplete search techniques for finding minimal, or at least small, tile sets and also assess the reliability of the solutions obtained according to the kinetic Tile Assembly Model.
Given a boolean n by n matrix A we consider arithmetic circuits for computing the transformation x->Ax over different semirings. Namely, we study three circuit models: monotone OR-circuits, monotone SUM-circuits (addition of non-negative integers), and non-monotone XOR-circuits (addition modulo 2). Our focus is on \emph{separating} these models in terms of their circuit complexities. We give three results towards this goal: (1) We prove a direct sum type theorem on the monotone complexity of tensor product matrices. As a corollary, we obtain matrices that admit OR-circuits of size O(n), but require SUM-circuits of size Ω(n^{3/2}/\log^2n). (2) We construct so-called \emph{k-uniform} matrices that admit XOR-circuits of size O(n), but require OR-circuits of size Ω(n^2/\log^2n). (3) We consider the task of \emph{rewriting} a given OR-circuit as a XOR-circuit and prove that any subquadratic-time algorithm for this task violates the strong exponential time hypothesis.
Do unique node identifiers help in deciding whether a network G has a prescribed property P? We study this question in the context of distributed local decision, where the objective is to decide whether G∈P by having each node run a constant-time distributed decision algorithm. If G∈P, all the nodes should output yes; if G∈/P, at least one node should output no. A recent work (Fraigniaud et al., OPODIS 2012) studied the role of identifiers in local decision and gave several conditions under which identifiers are not needed. In this article, we answer their original question. More than that, we do so under all combinations of the following two critical variations on the underlying model of distributed computing: (B): the size of the identifiers is bounded by a function of the size of the input network; as opposed to (¬B): the identifiers are unbounded. (C): the nodes run a computable algorithm; as opposed to (¬C): the nodes can compute any, possibly uncomputable function. While it is easy to see that under (¬B,¬C) identifiers are not needed, we show that under all other combinations there are properties that can be decided locally if and only if identifiers are present. Our constructions use ideas from classical computability theory.
In the study of deterministic distributed algorithms it is commonly assumed that each node has a unique O(logn)-bit identifier. We prove that for a general class of graph problems, local algorithms (constant-time distributed algorithms) do not need such identifiers: a port numbering and orientation is sufficient. Our result holds for so-called simple PO-checkable graph optimisation problems; this includes many classical packing and covering problems such as vertex covers, edge covers, matchings, independent sets, dominating sets, and edge dominating sets. We focus on the case of bounded-degree graphs and show that if a local algorithm finds a constant-factor approximation of a simple PO-checkable graph problem with the help of unique identifiers, then the same approximation ratio can be achieved on anonymous networks. As a corollary of our result and by prior work, we derive a tight lower bound on the local approximability of the minimum edge dominating set problem. Our main technical tool is an algebraic construction of homogeneously ordered graphs: We say that a graph is (α,r)-homogeneous if its nodes are linearly ordered so that an α fraction of nodes have pairwise isomorphic radius-r neighbourhoods. We show that there exists a finite (α,r)-homogeneous 2k-regular graph of girth at least g for any α<1 and any r, k, and g.
König's theorem states that on bipartite graphs the size of a maximum matching equals the size of a minimum vertex cover. It is known from prior work that for every ε> 0 there exists a constant-time distributed algorithm that finds a (1+ε)-approximation of a maximum matching on 2-coloured graphs of bounded degree. In this work, we show---somewhat surprisingly---that no sublogarithmic-time approximation scheme exists for the dual problem: there is a constant δ> 0 so that no randomised distributed algorithm with running time o(\log n) can find a (1+δ)-approximation of a minimum vertex cover on 2-coloured graphs of maximum degree 3. In fact, a simple application of the Linial--Saks (1993) decomposition demonstrates that this lower bound is tight. Our lower-bound construction is simple and, to some extent, independent of previous techniques. Along the way we prove that a certain cut minimisation problem, which might be of independent interest, is hard to approximate locally on expander graphs.
The Pattern self-Assembly Tile set Synthesis (PATS) problem is to determine a set of coloured tiles that self-assemble to implement a given rectangular colour pattern. We give an exhaustive branch-and-bound algorithm to find tile sets of minimum cardinality for the PATS problem. Our algorithm makes use of a search tree in the lattice of partitions of the ambient rectangular grid, and an efficient bounding function to prune this search tree. Empirical data on the performance of the algorithm shows that it compares favourably to previously presented heuristic solutions to the problem.
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.