all research papers
post-ai
All research papers listed below were developed post-AI.
Polynomial Interpolation for Sherali-Adams Lower Bounds
Nathan Acheampong, Ben Davis, Robert Robere
We prove Sherali-Adams is exponentially weaker than Res(2), and also that it is not automatable unless P = NP. This resolves an open question asked by many papers on the automatability of weak proof systems.
Submitted to STOC 2027.
Hard Instances for Strong Semantic Proof Systems: CNFs for Depth-Four PC and Deep Instances for \(AC^0\)[2]-Frege
Yaroslav Alekseev, Svyatoslav Gryaznov, Dmitry Itsykson, Toniann Pitassi, Robert Robere, Iddo Tzameret.
We extend recent lower bounds for the Res(+) proof system, due to Braun, to several semantic algebraic proof systems. We prove numerous lower bounds for these systems, and also exhibit a depth hierarchy theorem for \(AC^0[2]\)-Frege system for depth-\(d\) formulas.
Submitted to STOC 2027.
Progress on \(AC^0[2]\)-Frege Lower Bounds
Yaroslav Alekseev, Svyatoslav Gryaznov, Toniann Pitassi, Robert Robere, Alexander Shekhovtsov, Iddo Tzameret
We further improve the best known lower bounds against fragments of \(AC^0[2]\)-Frege proof systems, using techniques derived from the new exponential correlation bounds for polynomials by Chattopadhyay, Hatami, Lee, Lovett, Tal, and Viola. Our strongest bounds are superpolynomial for the fragment of depth-3.5 \(AC^0[2]\)-Frege proofs whose lines have the pattern \(\lor\land\oplus\land^{[b]}\), where \(b = o(\sqrt{\log n})\). Thanks to a known depth reduction of Buss, Kolodziejczyk, and Zdanowski, any polynomial-size \(AC^0[2]\)-Frege refutation can be reduced to this fragment in quasi-polynomial size where \(b = (\log n)^{O(1)}\). Hence our bounds are nearly at the threshold of what is attainable before proving lower bounds against arbitrary constant depth \(AC^0[2]\)-Frege.
Submitted to STOC 2027.
Lower Bounds Between Random CNFs and PRG Tautologies for Dag-like Communication
Duri Andrea Janett, Robert Robere, Anastasia Sofronova, Dmitry Sokolov
We prove new lower bounds on the length of Cutting Planes proofs for formulas which can be viewed as formally “between” random \(\Theta(\log n)\)-width CNFs, and PRG tautologies based on the Nisan-Wigderson generator. This requires developing a new technique for Cutting Planes lower bounds using the method of approximations, applied directly to the underlying triangle-DAG.
Submitted to STOC 2027.
pre-ai
All research papers listed below were developed completely independent of AI.
Provable Reductions in TFNP
Noah Fleming, Stefan Grosser, Toniann Pitassi, Robert Robere
We develop a new approach to implicit proof systems using white-box TFNP classes. In our new theory, an implicit proof can be viewed as a many-one reduction from the false-clause search problem associated with an unsatisfiable CNF formula to a problem in TFNP, coupled with an Extended Frege proof that the reduction is correct. Using this, we prove a new characterization of implicit Resolution, resolving an open problem posed by Krajicek.
To appear at ITCS 2027.
Lower Bounds for Approximate Sign-Rank
Riju Bindua, Hamed Hatami, Hasti Karimi, Robert Robere
We develop a new technique for proving lower bounds against approximate sign rank, which is a randomized variant of sign-rank introduced in the context of learning theory by Chornomaz, Moran, and Waknine. Formally, we show that any \(m \times n\) sign matrix with approximate sign-rank \(d\) contains a monochromatic rectangle of size \(d^{-O(d)} \times d^{-O(d^2)}\), which parallels existing results for sign rank. As a result, we obtain the first super-constant lower bounds for approximate sign-rank, as well as obtaining strong separations between approximate sign-rank and regular sign rank.
The key ingredient of our proof is a new geometric theorem on hyperplane avoidance, which we believe to be of independent interest.
To appear at ITCS 2027.
Res(log) Proves Bounded-Depth Frege Lower Bounds
Ben Davis, Robert Robere
We show, in certain parameter regimes, that Res(log) can formalize lower bounds against all of bounded-depth Frege. Formally, we show that Res(log) can prove that any depth-\(d\) Frege refutation of the Pigeonhole Principle, in which every line is restricted to have size \(n^{O(1)}\), requires exponentially many lines. This extends a recent formalization of a similar result for Resolution lower bounds in Res(log) by Li, Li, and Ren.
To appear at ITCS 2027.
On Pigeonhole Principles and Ramsey in TFNP
Black-Box PPP is Not Turing-Closed
Noah Fleming, Stefan Grosser, Toniann Pitassi, Robert Robere.
STOC 2024. [ECCC]
Intersection Classes in TFNP and Proof Complexity
Yuhao Li, William Pires, Robert Robere
ITCS 2024. [DROPS]
Colourful TFNP and Propositional Proofs
Ben Davis and Robert Robere.
CCC 2023. [ECCC]
On Low End Obfuscation and Learning
Elette Boyle, Yuval Ishai, Pierre Meyer, Robert Robere, Gal Yehuda.
ITCS 2023. [DROPS]
Separations in Proof Complexity and TFNP
Further Collapses in TFNP
Proofs, Circuits, and Communication
Susanna de Rezende, Mika Göös, Robert Robere.
SIGACT News Complexity Theory Column, March 2022. [ArXiV] [Talk at BIRS]
Extremely Deep Proofs
Noah Fleming, Toniann Pitassi, Robert Robere
ITCS 2022. [ECCC] [Talk at ITCS]
Pseudorandom Self-Reductions for NP-Complete Problems
Reyad Abed Elrazik, Robert Robere, Assaf Schuster, Gal Yehuda.
ITCS 2022. [ECCC] [Talk at ITCS]
On Semi-Algebraic Proofs and Algorithms
Noah Fleming, Mika Göös, Stefan Grosser, Robert Robere
ITCS 2022. [ECCC] [Talk at ITCS]
Amortized Circuit Complexity, Formal Complexity Measures, and Catalytic Algorithms
Robert Robere, Jeroen Zuiddam.
FOCS 2021. [ECCC] [Talk at FOCS] [Talk at IAS]
On the Power and Limitations of Branch and Cut
Automating Algebraic Proof Systems is NP-Hard
Susanna F. de Rezende, Mika Göös, Jakob Nördstrom, Toniann Pitassi, Robert Robere, Dmitry Sokolov.
STOC 2021. [ECCC]
KRW Composition Theorems via Lifting
Susanna F. de Rezende, Or Meir, Jakob Nördstrom, Toniann Pitassi, Robert Robere
FOCS 2020. [ECCC]
Lifting with Simple Gadgets and Applications to Circuit and Proof Complexity
Susanna F. de Rezende, Or Meir, Jakob Nördstrom, Toniann Pitassi, Robert Robere, Marc Vinyals.
FOCS 2020. [ECCC]
Lower Bounds for (Non-monotone) Comparator Circuits
Nullstellensatz Size-Degree Trade-Offs from Reversible Pebbling
Suzanna F. de Rezende, Or Meir, Jakob Nördstrom, Robert Robere.
Adventures in Monotone Complexity and TFNP
Learning-Sensitive Backdoors with Restarts
Edward Zulkoski, Ruben Martins, Christoph M. Wintersteiger, Robert Robere, Jia Liang, Krzysztof Czarnecki and Vijay Ganesh
CP 2018.
The Proof Complexity of SMT Solvers
Robert Robere, Antonina Kolokolova, Vijay Ganesh.
CAV 2018.
Lifting Nullstellensatz to Monotone Span Programs over any Field.
Toniann Pitassi, Robert Robere.
STOC 2018. [ECCC] [Talk at Simons Institute]
Stabbing Planes.
Paul Beame, Noah Fleming, Russell Impagliazzo, Antonina Kolokolova, Denis Pankratov, Toniann Pitassi, Robert Robere.
ITCS 2018. [ECCC]
Random Θ(log n)-CNFs are Hard for Cutting Planes.
Noah Fleming, Denis Pankratov, Toniann Pitassi, Robert Robere.
FOCS 2017. [ECCC]
J. ACM 69(3) (2022)
Strongly Exponential Lower Bounds for Monotone Computation.
Exponential Lower Bounds for Monotone Span Programs.
Robert Robere, Toniann Pitassi, Benjamin Rossman, Stephen A. Cook.
FOCS 2016. [ECCC] [Slides] [Talk at BIRS] [Talk at FOCS 2016]
Invited to the special journal issue for FOCS 2016.
When Thinking Never Comes To A Halt: Using Formal Methods in Making Sure Your AI Gets the Job Done Good Enough
Tarek R. Besold and Robert Robere
Fundamental Issues of Artificial Intelligence (2016). Volume 376:43-62. [DOI]
Path Graphs, Clique Trees, and Flowers.
Lalla Mouatadid and Robert Robere.
Manuscript 2015. [ArXiv]
When Almost Is Not Even Close: Remarks on the Approximability of HDTP.
Tarek R. Besold and Robert Robere.
AGI 2013. [DOI]
Awarded the Cognitive Science Society Prize for Best Student Paper.
A Note on Tractability and Artificial Intelligence.
Tarek R. Besold and Robert Robere.
AGI 2013. [DOI]
Average Case Lower Bounds for Monotone Switching Networks.
Stephen A. Cook, Yuval Filmus, Toniann Pitassi, Robert Robere.
FOCS 2013. [ECCC]
Complex Analogies: Remarks on the Complexity of HDTP.
Tarek R. Besold and Robert Robere.
Australasian Conference on Artificial Intelligence (AI 2012). [DOI]
A Change for the Better? Assessing the Computational Cost of Re-representation.
Todd Wareham, Robert Robere and Iris van Rooij.
International Conference on Cognitive Modeling [ICCM 2012].
theses
My Masters and PhD theses.