Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Toniann Pitassi:

TR21-012 | 9th February 2021
Noah Fleming, Mika Göös, Russell Impagliazzo, Toniann Pitassi, Robert Robere, Li-Yang Tan, Avi Wigderson

On the Power and Limitations of Branch and Cut

The Stabbing Planes proof system was introduced to model the reasoning carried out in practical mixed integer programming solvers. As a proof system, it is powerful enough to simulate Cutting Planes and to refute the Tseitin formulas -- certain unsatisfiable systems of linear equations mod 2 -- which are canonical ... more >>>

TR20-111 | 24th July 2020
Ian Mertz, Toniann Pitassi

Lifting: As Easy As 1,2,3

Revisions: 1

Query-to-communication 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 tree-like and dag-like settings). Whereas previous proofs used sophisticated Fourier analytic techniques, our proof uses elementary counting together with ... more >>>

TR20-099 | 6th July 2020
Susanna de Rezende, Or Meir, Jakob Nordström, Toniann Pitassi, Robert Robere

KRW Composition Theorems via Lifting

Revisions: 1

One of the major open problems in complexity theory is proving super-logarithmic lower bounds on the depth of circuits (i.e., $\mathbf{P}\not\subseteq\mathbf{NC}^1$). Karchmer, Raz, and Wigderson (Computational Complexity 5(3/4), 1995) suggested to approach this problem by proving that depth complexity behaves “as expected” with respect to the composition of functions $f ... more >>>

TR20-064 | 2nd May 2020
Mika Göös, Jakob Nordström, Toniann Pitassi, Robert Robere, Dmitry Sokolov, Susanna de Rezende

Automating Algebraic Proof Systems is NP-Hard

Revisions: 1

We show that algebraic proofs are hard to find: Given an unsatisfiable CNF formula $F$, it is NP-hard to find a refutation of $F$ in the Nullstellensatz, Polynomial Calculus, or Sherali--Adams proof systems in time polynomial in the size of the shortest such refutation. Our work extends, and gives a ... more >>>

TR20-049 | 17th April 2020
Mika Göös, Sajin Koroth, Ian Mertz, Toniann Pitassi

Automating Cutting Planes is NP-Hard

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 ... more >>>

TR19-186 | 31st December 2019
Or Meir, Jakob Nordström, Toniann Pitassi, Robert Robere, Susanna de Rezende

Lifting with Simple Gadgets and Applications to Circuit and Proof Complexity

Revisions: 4

We significantly strengthen and generalize the theorem lifting Nullstellensatz degree to monotone span program size by Pitassi and Robere (2018) so that it works for any gadget with high enough rank, in particular, for useful gadgets such as equality and greater-than. We apply our generalized theorem to solve two open ... more >>>

TR19-106 | 12th August 2019
Noah Fleming, Pravesh Kothari, Toniann Pitassi

Semialgebraic Proofs and Efficient Algorithm Design

Revisions: 4

Over the last twenty years, an exciting interplay has emerged between proof systems and algorithms. Some natural families of algorithms can be viewed as a generic translation from a proof that a solution exists into an algorithm for finding the solution itself. This connection has perhaps been the most consequential ... more >>>

TR19-103 | 7th August 2019
Arkadev Chattopadhyay, Yuval Filmus, Sajin Koroth, Or Meir, Toniann Pitassi

Query-to-Communication Lifting Using Low-Discrepancy Gadgets

Revisions: 2

Lifting theorems are theorems that relate the query complexity of a function $f:\left\{ 0,1 \right\}^n\to \left\{ 0,1 \right\}$ to the communication complexity of the composed function $f\circ g^n$, for some “gadget” $g:\left\{ 0,1 \right\}^b\times \left\{ 0,1 \right\}^b\to \left\{ 0,1 \right\}$. Such theorems allow transferring lower bounds from query complexity to ... more >>>

TR19-043 | 12th March 2019
Toniann Pitassi, Morgan Shirley, Thomas Watson

Nondeterministic and Randomized Boolean Hierarchies in Communication Complexity

We study the Boolean Hierarchy in the context of two-party communication complexity, as well as the analogous hierarchy defined with one-sided error randomness instead of nondeterminism. Our results provide a complete picture of the relationships among complexity classes within and across these two hierarchies. In particular, we prove a query-to-communication ... more >>>

TR19-024 | 20th February 2019
Russell Impagliazzo, Sasank Mouli, Toniann Pitassi

The Surprising Power of Constant Depth Algebraic Proofs

Revisions: 2

A major open problem in proof complexity is to prove super-polynomial lower bounds for AC^0[p]-Frege proofs. This system is the analog of AC^0[p], the class of bounded depth circuits with prime modular counting gates. Despite strong lower bounds for this class dating back thirty years (Razborov, '86 and Smolensky, '87), ... more >>>

TR17-165 | 3rd November 2017
Toniann Pitassi, Robert Robere

Lifting Nullstellensatz to Monotone Span Programs over Any Field

We characterize the size of monotone span programs computing certain "structured" boolean functions by the Nullstellensatz degree of a related unsatisfiable Boolean formula.

This yields the first exponential lower bounds for monotone span programs over arbitrary fields, the first exponential separations between monotone span programs over fields of different ... more >>>

TR17-151 | 8th October 2017
Paul Beame, Noah Fleming, Russell Impagliazzo, Antonina Kolokolova, Denis Pankratov, Toniann Pitassi, Robert Robere

Stabbing Planes

We introduce and develop a new semi-algebraic proof system, called Stabbing Planes that is in the style of DPLL-based modern SAT solvers. As with DPLL, there is only one rule: the current polytope can be subdivided by
branching on an inequality and its "integer negation.'' That is, we can (nondeterministically ... more >>>

TR17-053 | 22nd March 2017
Mika Göös, Toniann Pitassi, Thomas Watson

Query-to-Communication Lifting for BPP

Revisions: 1

For any $n$-bit boolean function $f$, we show that the randomized communication complexity of the composed function $f\circ g^n$, where $g$ is an index gadget, is characterized by the randomized decision tree complexity of $f$. In particular, this means that many query complexity separations involving randomized models (e.g., classical vs.\ ... more >>>

TR17-045 | 7th March 2017
Noah Fleming, Denis Pankratov, Toniann Pitassi, Robert Robere

Random CNFs are Hard for Cutting Planes

Revisions: 2

The random k-SAT model is the most important and well-studied distribution over
k-SAT instances. It is closely connected to statistical physics; it is used as a testbench for
satisfiablity algorithms, and lastly average-case hardness over this distribution has also
been linked to hardness of approximation via Feige’s hypothesis. In this ... more >>>

TR17-024 | 16th February 2017
Mika Göös, Pritish Kamath, Toniann Pitassi, Thomas Watson

Query-to-Communication Lifting for P^NP

Revisions: 1

We prove that the $\text{P}^{\small\text{NP}}$-type query complexity (alternatively, decision list width) of any boolean function $f$ is quadratically related to the $\text{P}^{\small\text{NP}}$-type communication complexity of a lifted version of $f$. As an application, we show that a certain "product" lower bound method of Impagliazzo and Williams (CCC 2010) fails to ... more >>>

TR16-188 | 21st November 2016
Toniann Pitassi, Robert Robere

Strongly Exponential Lower Bounds for Monotone Computation

For a universal constant $\alpha > 0$, we prove size lower bounds of $2^{\alpha N}$ for computing an explicit monotone function in NP in the following models of computation: monotone formulas, monotone switching networks, monotone span programs, and monotone comparator circuits, where $N$ is the number of variables of the ... more >>>

TR16-101 | 1st July 2016
Toniann Pitassi, Iddo Tzameret

Algebraic Proof Complexity: Progress, Frontiers and Challenges

We survey recent progress in the proof complexity of strong proof systems and its connection to algebraic circuit complexity, showing how the synergy between the two gives rise to new approaches to fundamental open questions, solutions to old problems, and new directions of research. In particular, we focus on tight ... more >>>

TR16-064 | 19th April 2016
Stephen A. Cook, Toniann Pitassi, Robert Robere, Benjamin Rossman

Exponential Lower Bounds for Monotone Span Programs

Monotone span programs are a linear-algebraic model of computation which were introduced by Karchmer and Wigderson in 1993. They are known to be equivalent to linear secret sharing schemes, and have various applications in complexity theory and cryptography. Lower bounds for monotone span programs have been difficult to obtain because ... more >>>

TR15-169 | 23rd October 2015
Mika Göös, T.S. Jayram, Toniann Pitassi, Thomas Watson

Randomized Communication vs. Partition Number

Revisions: 1

We show that \emph{randomized} communication complexity can be superlogarithmic in the partition number of the associated communication matrix, and we obtain near-optimal \emph{randomized} lower bounds for the Clique vs.\ Independent Set problem. These results strengthen the deterministic lower bounds obtained in prior work (G\"o\"os, Pitassi, and Watson, {\small FOCS~2015}).

more >>>

TR15-050 | 4th April 2015
Mika Göös, Toniann Pitassi, Thomas Watson

Deterministic Communication vs. Partition Number

Revisions: 1

We show that deterministic communication complexity can be superlogarithmic in the partition number of the associated communication matrix. We also obtain near-optimal deterministic lower bounds for the Clique vs. Independent Set problem, which in particular yields new lower bounds for the log-rank conjecture. All these results follow from a simple ... more >>>

TR15-049 | 3rd April 2015
Mika Göös, Toniann Pitassi, Thomas Watson

The Landscape of Communication Complexity Classes

Revisions: 1

We prove several results which, together with prior work, provide a nearly-complete picture of the relationships among classical communication complexity classes between $P$ and $PSPACE$, short of proving lower bounds against classes for which no explicit lower bounds were already known. Our article also serves as an up-to-date survey on ... more >>>

TR14-078 | 7th June 2014
Mika Göös, Toniann Pitassi, Thomas Watson

Zero-Information Protocols and Unambiguity in Arthur-Merlin Communication

We study whether information complexity can be used to attack the long-standing open problem of proving lower bounds against Arthur--Merlin (AM) communication protocols. Our starting point is to show that---in contrast to plain randomized communication complexity---every boolean function admits an AM communication protocol where on each yes-input, the distribution of ... more >>>

TR14-052 | 14th April 2014
Joshua Grochow, Toniann Pitassi

Circuit complexity, proof complexity, and polynomial identity testing

We introduce a new and very natural algebraic proof system, which has tight connections to (algebraic) circuit complexity. In particular, we show that any super-polynomial lower bound on any Boolean tautology in our proof system implies that the permanent does not have polynomial-size algebraic circuits ($VNP \neq VP$). As a ... more >>>

TR13-054 | 4th April 2013
Yuval Filmus, Toniann Pitassi, Robert Robere, Stephen A. Cook

Average Case Lower Bounds for Monotone Switching Networks

Revisions: 1

An approximate computation of a Boolean function by a circuit or switching network is a computation which computes the function correctly on the majority of the inputs (rather than on all inputs). Besides being interesting in their own right, lower bounds for approximate computation have proved useful in many subareas ... more >>>

TR11-106 | 6th August 2011
Andrew McGregor, Ilya Mironov, Toniann Pitassi, Omer Reingold, Kunal Talwar, Salil Vadhan

The Limits of Two-Party Differential Privacy

We study differential privacy in a distributed setting where two parties would like to perform analysis of their joint data while preserving privacy for both datasets. Our results imply almost tight lower bounds on the accuracy of such data analyses, both for specific natural functions (such as Hamming distance) and ... more >>>

ISSN 1433-8092 | Imprint