All reports by Author Noah Fleming:

__
TR24-010
| 19th January 2024
__

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

Revisions: 1

__
TR23-052
| 19th April 2023
__

Noah Fleming, Vijay Ganesh, Antonina Kolokolova, Chunxiao Li, Marc Vinyals#### Limits of CDCL Learning via Merge Resolution

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

Noah Fleming, Vijay Ganesh, Antonina Kolokolova, Chunxiao Li, Marc Vinyals

In their seminal work, Atserias et al. and independently Pipatsrisawat and Darwiche in 2009 showed that CDCL solvers can simulate resolution proofs with polynomial overhead. However, previous work does not address the tightness of the simulation, i.e., the question of how large this overhead needs to be. In this paper, ... more >>>