All reports by Author Toniann Pitassi:

__
TR24-076
| 10th April 2024
__

Oliver Korten, Toniann Pitassi#### Strong vs. Weak Range Avoidance and the Linear Ordering Principle

__
TR24-010
| 19th January 2024
__

Noah Fleming, Stefan Grosser, Toniann Pitassi, Robert Robere#### Black-Box PPP is not Turing-Closed

Revisions: 1

__
TR23-138
| 12th September 2023
__

Lianna Hambardzumyan, Toniann Pitassi, Suhail Sherif, Morgan Shirley, Adi Shraibman#### An improved protocol for ExactlyN with more than 3 players

__
TR22-152
| 10th November 2022
__

Toniann Pitassi, Morgan Shirley, Adi Shraibman#### The Strength of Equality Oracles in Communication

__
TR22-038
| 13th March 2022
__

Russell Impagliazzo, Sasank Mouli, Toniann Pitassi#### Lower bounds for Polynomial Calculus with extension variables over finite fields

Revisions: 1

__
TR22-006
| 12th January 2022
__

Benny Applebaum, Amos Beimel, Oded Nir, Naty Peter, Toniann Pitassi#### Secret Sharing, Slice Formulas, and Monotone Real Circuits

__
TR21-158
| 12th November 2021
__

Noah Fleming, Toniann Pitassi, Robert Robere#### Extremely Deep Proofs

Revisions: 1

__
TR21-061
| 29th April 2021
__

Noah Fleming, Toniann Pitassi#### Reflections on Proof Complexity and Counting Principles

__
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

Revisions: 2

__
TR20-111
| 24th July 2020
__

Ian Mertz, Toniann Pitassi#### Lifting: As Easy As 1,2,3

Revisions: 1

__
TR20-099
| 6th July 2020
__

Susanna de Rezende, Or Meir, Jakob Nordström, Toniann Pitassi, Robert Robere#### KRW Composition Theorems via Lifting

Revisions: 1

__
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: 2

__
TR20-049
| 17th April 2020
__

Mika Göös, Sajin Koroth, Ian Mertz, Toniann Pitassi#### Automating Cutting Planes is NP-Hard

__
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

__
TR19-106
| 12th August 2019
__

Noah Fleming, Pravesh Kothari, Toniann Pitassi#### Semialgebraic Proofs and Efficient Algorithm Design

Revisions: 5

__
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

__
TR19-043
| 12th March 2019
__

Toniann Pitassi, Morgan Shirley, Thomas Watson#### Nondeterministic and Randomized Boolean Hierarchies in Communication Complexity

Revisions: 1

__
TR19-024
| 20th February 2019
__

Russell Impagliazzo, Sasank Mouli, Toniann Pitassi#### The Surprising Power of Constant Depth Algebraic Proofs

Revisions: 2

__
TR17-165
| 3rd November 2017
__

Toniann Pitassi, Robert Robere#### Lifting Nullstellensatz to Monotone Span Programs over Any Field

__
TR17-151
| 8th October 2017
__

Paul Beame, Noah Fleming, Russell Impagliazzo, Antonina Kolokolova, Denis Pankratov, Toniann Pitassi, Robert Robere#### Stabbing Planes

Revisions: 3

__
TR17-053
| 22nd March 2017
__

Mika Göös, Toniann Pitassi, Thomas Watson#### Query-to-Communication Lifting for BPP

Revisions: 1

__
TR17-045
| 7th March 2017
__

Noah Fleming, Denis Pankratov, Toniann Pitassi, Robert Robere#### Random CNFs are Hard for Cutting Planes

Revisions: 2

__
TR17-024
| 16th February 2017
__

Mika Göös, Pritish Kamath, Toniann Pitassi, Thomas Watson#### Query-to-Communication Lifting for P^NP

Revisions: 1

__
TR16-188
| 21st November 2016
__

Toniann Pitassi, Robert Robere#### Strongly Exponential Lower Bounds for Monotone Computation

__
TR16-101
| 1st July 2016
__

Toniann Pitassi, Iddo Tzameret#### Algebraic Proof Complexity: Progress, Frontiers and Challenges

__
TR16-064
| 19th April 2016
__

Stephen A. Cook, Toniann Pitassi, Robert Robere, Benjamin Rossman#### Exponential Lower Bounds for Monotone Span Programs

__
TR15-169
| 23rd October 2015
__

Mika Göös, T.S. Jayram, Toniann Pitassi, Thomas Watson#### Randomized Communication vs. Partition Number

Revisions: 1

__
TR15-050
| 4th April 2015
__

Mika Göös, Toniann Pitassi, Thomas Watson#### Deterministic Communication vs. Partition Number

Revisions: 1

__
TR15-049
| 3rd April 2015
__

Mika Göös, Toniann Pitassi, Thomas Watson#### The Landscape of Communication Complexity Classes

Revisions: 1

__
TR14-078
| 7th June 2014
__

Mika Göös, Toniann Pitassi, Thomas Watson#### Zero-Information Protocols and Unambiguity in Arthur-Merlin Communication

__
TR14-052
| 14th April 2014
__

Joshua Grochow, Toniann Pitassi#### Circuit complexity, proof complexity, and polynomial identity testing

__
TR13-054
| 4th April 2013
__

Yuval Filmus, Toniann Pitassi, Robert Robere, Stephen A. Cook#### Average Case Lower Bounds for Monotone Switching Networks

Revisions: 1

__
TR11-106
| 6th August 2011
__

Andrew McGregor, Ilya Mironov, Toniann Pitassi, Omer Reingold, Kunal Talwar, Salil Vadhan#### The Limits of Two-Party Differential Privacy

Oliver Korten, Toniann Pitassi

In a pair of recent breakthroughs \cite{CHR,Li} it was shown that the classes $S_2^E, ZPE^{NP}$, and $\Sigma_2^E$ require exponential circuit complexity, giving the first unconditional improvements to a classical result of Kannan. These results were obtained by designing a surprising new algorithm for the total search problem Range Avoidance: given ... more >>>

Noah Fleming, Stefan Grosser, Toniann Pitassi, Robert Robere

The complexity class PPP contains all total search problems many-one reducible to the PIGEON problem, where we are given a succinct encoding of a function mapping n+1 pigeons to n holes, and must output two pigeons that collide in a hole. PPP is one of the “original five” syntactically-defined subclasses ... more >>>

Lianna Hambardzumyan, Toniann Pitassi, Suhail Sherif, Morgan Shirley, Adi Shraibman

The ExactlyN problem in the number-on-forehead (NOF) communication setting asks $k$ players, each of whom can see every input but their own, if the $k$ input numbers add up to $N$. Introduced by Chandra, Furst and Lipton in 1983, ExactlyN is important for its role in understanding the strength of ... more >>>

Toniann Pitassi, Morgan Shirley, Adi Shraibman

It is well-known that randomized communication protocols are more powerful than deterministic protocols. In particular the Equality function requires $\Omega(n)$ deterministic communication complexity but has efficient randomized protocols. Previous work of Chattopadhyay, Lovett and Vinyals shows that randomized communication is strictly stronger than what can be solved by deterministic protocols ... more >>>

Russell Impagliazzo, Sasank Mouli, Toniann Pitassi

For every prime p > 0, every n > 0 and ? = O(logn), we show the existence

of an unsatisfiable system of polynomial equations over O(n log n) variables of degree O(log n) such that any Polynomial Calculus refutation over F_p with M extension variables, each depending on at ...
more >>>

Benny Applebaum, Amos Beimel, Oded Nir, Naty Peter, Toniann Pitassi

A secret-sharing scheme allows to distribute a secret $s$ among $n$ parties such that only some predefined ``authorized'' sets of parties can reconstruct the secret, and all other ``unauthorized'' sets learn nothing about $s$. For over 30 years, it was known that any (monotone) collection of authorized sets can be ... more >>>

Noah Fleming, Toniann Pitassi, Robert Robere

We further the study of supercritical tradeoffs in proof and circuit complexity, which is a type of tradeoff between complexity parameters where restricting one complexity parameter forces another to exceed its worst-case upper bound. In particular, we prove a new family of supercritical tradeoffs between depth and size for Resolution, ... more >>>

Noah Fleming, Toniann Pitassi

This paper surveys the development of propositional proof complexity and the seminal contributions of Alasdair Urquhart. We focus on the central role of counting principles, and in particular Tseitin's graph tautologies, to most of the key advances in lower bounds in proof complexity. We reflect on a couple of key ... more >>>

Noah Fleming, Mika Göös, Russell Impagliazzo, Toniann Pitassi, Robert Robere, Li-Yang Tan, Avi Wigderson

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

Ian Mertz, Toniann Pitassi

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

Susanna de Rezende, Or Meir, Jakob Nordström, Toniann Pitassi, Robert Robere

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

Mika Göös, Jakob Nordström, Toniann Pitassi, Robert Robere, Dmitry Sokolov, Susanna de Rezende

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

Mika Göös, Sajin Koroth, Ian Mertz, Toniann Pitassi

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

Or Meir, Jakob Nordström, Toniann Pitassi, Robert Robere, Susanna de Rezende

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

Noah Fleming, Pravesh Kothari, Toniann Pitassi

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

Arkadev Chattopadhyay, Yuval Filmus, Sajin Koroth, Or Meir, Toniann Pitassi

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

Toniann Pitassi, Morgan Shirley, Thomas Watson

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

Russell Impagliazzo, Sasank Mouli, Toniann Pitassi

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

Toniann Pitassi, Robert Robere

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

Paul Beame, Noah Fleming, Russell Impagliazzo, Antonina Kolokolova, Denis Pankratov, Toniann Pitassi, Robert Robere

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

Mika Göös, Toniann Pitassi, Thomas Watson

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

Noah Fleming, Denis Pankratov, Toniann Pitassi, Robert Robere

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

Mika Göös, Pritish Kamath, Toniann Pitassi, Thomas Watson

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

Toniann Pitassi, Robert Robere

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

Toniann Pitassi, Iddo Tzameret

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

Stephen A. Cook, Toniann Pitassi, Robert Robere, Benjamin Rossman

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

Mika Göös, T.S. Jayram, Toniann Pitassi, Thomas Watson

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 >>>Mika Göös, Toniann Pitassi, Thomas Watson

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

Mika Göös, Toniann Pitassi, Thomas Watson

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

Mika Göös, Toniann Pitassi, Thomas Watson

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

Joshua Grochow, Toniann Pitassi

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

Yuval Filmus, Toniann Pitassi, Robert Robere, Stephen A. Cook

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

Andrew McGregor, Ilya Mironov, Toniann Pitassi, Omer Reingold, Kunal Talwar, Salil Vadhan

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