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.

[ECCC]

Talk at Newton Institute (October 2026), [Part 1], [Part 2]

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.

[PDF]

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.

[PDF]

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.

[PDF]

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.

[PDF]

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.

[ArXiV]

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.

[ECCC]

On Pigeonhole Principles and Ramsey in TFNP

Siddhartha Jain, Jiawei Li, Robert Robere, Zhiyang Xun

FOCS 2024. [ECCC] [ArXiV]

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

Mika Göös, Alexandros Hollender, Siddhartha Jain, Gilbert Maystre, William Pires, Robert Robere, Ran Tao.

FOCS 2022. [ECCC]

Journal of the ACM (2024). [ACM DL]

Further Collapses in TFNP

Mika Göös, Alexandros Hollender, Siddhartha Jain, Gilbert Maystre, William Pires, Robert Robere, Ran Tao.

CCC 2022. [ECCC] [DROPS]

Contributed presentation at HALG 2022.

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

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

CCC 2021. [ECCC] [arXiv]

Invited to the special journal issue for CCC 2021.

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

Anna Gál, Robert Robere

ITCS 2020. [ECCC] [DROPS]

Nullstellensatz Size-Degree Trade-Offs from Reversible Pebbling

Suzanna F. de Rezende, Or Meir, Jakob Nördstrom, Robert Robere.

CCC 2019. [ECCC] [DROPS]

Computational Complexity 30, 4 (2021)

Adventures in Monotone Complexity and TFNP

Mika Göös, Pritish Kamath, Robert Robere, Dmitry Sokolov

ITCS 2019. [ECCC] [DROPS]

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.

Toniann Pitassi, Robert Robere.

STOC 2017. [ECCC] [Slides]

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.