Querytocommunication lifting theorems translate lower bounds on query complexity to lower bounds for the corresponding communication model. In this paper, we give a simplified proof of deterministic lifting (in both the treelike and daglike settings). Our proof uses elementary counting together with a novel connection to the sunflower lemma.
In addition to a simplified proof, our approach opens up a new avenue of attack towards proving lifting theorems with improved gadget size  one of the main challenges in the area. Focusing on one of the most widely used gadgets  the index gadget  existing lifting techniques are known to require at least a quadratic gadget size. Our new approach combined with robust sunflower lemmas allows us to reduce the gadget size to near linear. We conjecture that it can be further improved to polylogarithmic, similar to the known bounds for the corresponding robust sunflower lemmas.
more »
« less
TFNP Characterizations of Proof Systems and Monotone Circuits
Connections between proof complexity and circuit complexity have become major tools for obtaining lower bounds in both areas. These connections  which take the form of interpolation theorems and querytocommunication lifting theorems  translate efficient proofs into small circuits, and vice versa, allowing tools from one area to be applied to the other. Recently, the theory of TFNP has emerged as a unifying framework underlying these connections. For many of the proof systems which admit such a connection there is a TFNP problem which characterizes it: the class of problems which are reducible to this TFNP problem via queryefficient reductions is equivalent to the tautologies that can be efficiently proven in the system. Through this, proof complexity has become a major tool for proving separations in blackbox TFNP. Similarly, for certain monotone circuit models, the class of functions that it can compute efficiently is equivalent to what can be reduced to a certain TFNP problem in a communicationefficient manner. When a TFNP problem has both a proof and circuit characterization, one can prove an interpolation theorem. Conversely, many lifting theorems can be viewed as relating the communication and query reductions to TFNP problems. This is exciting, as it suggests that TFNP provides a roadmap for the development of further interpolation theorems and lifting theorems.
In this paper we begin to develop a more systematic understanding of when these connections to TFNP occur. We give exact conditions under which a proof system or circuit model admits a characterization by a TFNP problem. We show:
 Every wellbehaved proof system which can prove its own soundness (a reflection principle) is characterized by a TFNP problem. Conversely, every TFNP problem gives rise to a wellbehaved proof system which proves its own soundness.
 Every wellbehaved monotone circuit model which admits a universal family of functions is characterized by a TFNP problem. Conversely, every TFNP problem gives rise to a wellbehaved monotone circuit model with a universal problem. As an example, we provide a TFNP characterization of the Polynomial Calculus, answering a question from [Mika Göös et al., 2022], and show that it can prove its own soundness.
more »
« less
 Award ID(s):
 2212135
 NSFPAR ID:
 10531031
 Editor(s):
 Tauman_Kalai, Yael
 Publisher / Repository:
 Schloss Dagstuhl – LeibnizZentrum für Informatik
 Date Published:
 Volume:
 251
 ISSN:
 18688969
 ISBN:
 9783959772631
 Page Range / eLocation ID:
 251251
 Subject(s) / Keyword(s):
 Proof Complexity Circuit Complexity TFNP Theory of computation → Proof complexity
 Format(s):
 Medium: X Size: 40 pages; 1019347 bytes Other: application/pdf
 Size(s):
 40 pages 1019347 bytes
 Right(s):
 Creative Commons Attribution 4.0 International license; info:eurepo/semantics/openAccess
 Sponsoring Org:
 National Science Foundation
More Like this


One of the major open problems in complexity theory is proving superlogarithmic lower bounds on the depth of circuits (i.e., P 6⊆ NC1). Karchmer, Raz, and Wigderson [KRW95] suggested to approach this problem by proving that depth complexity behaves “as expected” with respect to the composition of functions f ⋄ g. They showed that the validity of this conjecture would imply that P 6⊆ NC^1 . Several works have made progress toward resolving this conjecture by proving special cases. In particular, these works proved the KRW conjecture for every outer function f, but only for few inner functions g. Thus, it is an important challenge to prove the KRW conjecture for a wider range of inner functions. In this work, we extend significantly the range of inner functions that can be handled. First, we consider the monotone version of the KRW conjecture. We prove it for every monotone inner function g whose depth complexity can be lower bounded via a querytocommunication lifting theorem. This allows us to handle several new and wellstudied functions such as the stconnectivity, clique, and generation functions. In order to carry this progress back to the nonmonotone setting, we introduce a new notion of semimonotone composition, which combines the nonmonotone complexity of the outer function f with the monotone complexity of the inner function g. In this setting, we prove the KRW conjecture for a similar selection of inner functions g, but only for a specific choice of the outer function f.more » « less

null (Ed.)The complexity class ZPP NP[1] (corresponding to zeroerror randomized algorithms with access to one NP oracle query) is known to have a number of curious properties. We further explore this class in the settings of time complexity, query complexity, and communication complexity. • For starters, we provide a new characterization: ZPP NP[1] equals the restriction of BPP NP[1] where the algorithm is only allowed to err when it forgoes the opportunity to make an NP oracle query. • Using the above characterization, we prove a querytocommunication lifting theorem , which translates any ZPP NP[1] decision tree lower bound for a function f into a ZPP NP[1] communication lower bound for a twoparty version of f . • As an application, we use the above lifting theorem to prove that the ZPP NP[1] communication lower bound technique introduced by Göös, Pitassi, and Watson (ICALP 2016) is not tight. We also provide a “primal” characterization of this lower bound technique as a complexity class.more » « less

Querytocommunication lifting theorems, which connect the query complexity of a Boolean function to the communication complexity of an associated `lifted' function obtained by composing the function with many copies of another function known as a gadget, have been instrumental in resolving many open questions in computational complexity. Several important complexity questions could be resolved if we could make substantial improvements in the input size required for lifting with the Index function, from its current nearlinear size down to polylogarithmic in the number of inputs N of the original function or, ideally, constant. The nearlinear size bound was shown by Lovett, Meka, Mertz, Pitassi and Zhang using a recent breakthrough improvement on the Sunflower Lemma to show that a certain graph associated with the Index function of nearlinear size is a disperser. They also stated a conjecture about the Index function that is essential for further improvements in the size required for lifting with Index using current techniques. In this paper we prove the following; 1) The conjecture of Lovett et al. is false when the size of the Index gadget is logN−\omega(1). 2) Also, the InnerProduct function, which satisfies the disperser property at size O(logN), does not have this property when its size is log N−\omega(1). 3) Nonetheless, using Index gadgets of size at least 4, we prove a lifting theorem for a restricted class of communication protocols in which one of the players is limited to sending parities of its inputs. 4) Using the ideas from this lifting theorem, we derive a strong lifting theorem from decision tree size to parity decision tree size. We use this to derive a general lifting theorem in proof complexity from treeresolution size to treelike Res(\oplus) refutation size, which yields many new exponential lower bounds on such proofs.more » « less

Stefano Leonardi and Anupam Gupta (Ed.)A probabilistic algorithm A is pseudodeterministic if, on every input, there exists a canonical value that is output with high probability. If the algorithm outputs one of k canonical values with high probability, then it is called a kpseudodeterministic algorithm. In the study of pseudodeterminism, the Acceptance Probability Estimation Problem (APEP), which is to additively approximate the acceptance probability of a Boolean circuit, is emerging as a central computational problem. This problem admits a 2pseudodeterministic algorithm. Recently, it was shown that a pseudodeterministic algorithm for this problem would imply that any multivalued function that admits a kpseudodeterministic algorithm for a constant k (including approximation algorithms) also admits a pseudodeterministic algorithm (Dixon, Pavan, Vinodchandran; ITCS 2021). The contribution of the present work is twofold. First, as our main conceptual contribution, we establish that the existence of a pseudodeterministic algorithm for APEP is fundamentally related to the gap between probabilistic promise classes and the corresponding standard complexity classes. In particular, we show the following equivalence: APEP has a pseudodeterministic approximation algorithm if and only if every promise problem in PromiseBPP has a solution in BPP. A conceptual interpretation of this equivalence is that the algorithmic gap between 2pseudodeterminism and pseudodeterminism is equivalent to the gap between PromiseBPP and BPP. Based on this connection, we show that designing pseudodeterministic algorithms for APEP leads to the solution of some open problems in complexity theory, including new Boolean circuit lower bounds. This equivalence also explains how multipseudodeterminism is connected to problems in SearchBPP. In particular, we show that if APEP has a pseudodeterministic algorithm, then every problem that admits a k(n)pseudodeterministic algorithm (for any polynomial k) is in SearchBPP and admits a pseudodeterministic algorithm. Motivated by this connection, we also explore its connection to probabilistic search problems and establish that APEP is complete for certain notions of search problems in the context of pseudodeterminism. Our second contribution is establishing query complexity lower bounds for multipseudodeterministic computations. We prove that for every k ≥ 1, there exists a problem whose (k+1)pseudodeterministic query complexity, in the uniform query model, is O(1) but has a kpseudodeterministic query complexity of Ω(n), even in the more general nonadaptive query model. A key contribution of this part of the work is the utilization of Sperner’s lemma in establishing query complexity lower bounds.more » « less