Zobrazeno 1 - 10
of 42
pro vyhledávání: '"Robere, Robert"'
We show that the TFNP problem RAMSEY is not black-box reducible to PIGEON, refuting a conjecture of Goldberg and Papadimitriou in the black-box setting. We prove this by giving reductions to RAMSEY from a new family of TFNP problems that correspond t
Externí odkaz:
http://arxiv.org/abs/2401.12604
Autor:
Göös, Mika, Hollender, Alexandros, Jain, Siddhartha, Maystre, Gilbert, Pires, William, Robere, Robert, Tao, Ran
Publikováno v:
Journal of the ACM; Aug2024, Vol. 71 Issue 4, p1-45, 45p
Autor:
Göös, Mika, Hollender, Alexandros, Jain, Siddhartha, Maystre, Gilbert, Pires, William, Robere, Robert, Tao, Ran
Publikováno v:
Journal of the ACM, 71(4): Article 26 (2024)
It is well-known that Resolution proofs can be efficiently simulated by Sherali-Adams (SA) proofs. We show, however, that any such simulation needs to exploit huge coefficients: Resolution cannot be efficiently simulated by SA when the coefficients a
Externí odkaz:
http://arxiv.org/abs/2205.02168
Publikováno v:
SIGACT News Complexity Theory Column, March 2022
We survey lower-bound results in complexity theory that have been obtained via newfound interconnections between propositional proof complexity, boolean circuit complexity, and query/communication complexity. We advocate for the theory of total searc
Externí odkaz:
http://arxiv.org/abs/2202.08909
Autor:
Göös, Mika, Hollender, Alexandros, Jain, Siddhartha, Maystre, Gilbert, Pires, William, Robere, Robert, Tao, Ran
We show $\textsf{EOPL}=\textsf{PLS}\cap\textsf{PPAD}$. Here the class $\textsf{EOPL}$ consists of all total search problems that reduce to the End-of-Potential-Line problem, which was introduced in the works by Hubacek and Yogev (SICOMP 2020) and Fea
Externí odkaz:
http://arxiv.org/abs/2202.07761
Autor:
Fleming, Noah, Göös, Mika, Impagliazzo, Russell, Pitassi, Toniann, Robere, Robert, Tan, Li-Yang, Wigderson, Avi
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 unsat
Externí odkaz:
http://arxiv.org/abs/2102.05019
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 a
Externí odkaz:
http://arxiv.org/abs/2007.02740
We establish an exactly tight relation between reversible pebblings of graphs and Nullstellensatz refutations of pebbling formulas, showing that a graph $G$ can be reversibly pebbled in time $t$ and space $s$ if and only if there is a Nullstellensatz
Externí odkaz:
http://arxiv.org/abs/2001.02481
Autor:
de Rezende, Susanna F., Meir, Or, Nordström, Jakob, Pitassi, Toniann, Robere, Robert, Vinyals, Marc
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
Externí odkaz:
http://arxiv.org/abs/2001.02144
Autor:
Beame, Paul, Fleming, Noah, Impagliazzo, Russell, Kolokolova, Antonina, Pankratov, Denis, Pitassi, Toniann, Robere, Robert
We develop a new semi-algebraic proof system called Stabbing Planes which formalizes modern branch-and-cut algorithms for integer programming and is in the style of DPLL-based modern SAT solvers. As with DPLL there is only a single rule: the current
Externí odkaz:
http://arxiv.org/abs/1710.03219