Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > DAG-LIKE COMMUNICATION:
Reports tagged with dag-like communication:
TR22-046 | 4th April 2022
Dmitry Itsykson, Artur Riazanov

Automating OBDD proofs is NP-hard

We prove that the proof system OBDD(and, weakening) is not automatable unless P = NP. The proof is based upon the celebrated result of Atserias and Muller [FOCS 2019] about the hardness of automatability for resolution. The heart of the proof is lifting with a multi-output indexing gadget from resolution ... more >>>


TR25-057 | 28th April 2025
Paul Beame, Michael Whitmeyer

Multiparty Communication Complexity of Collision-Finding and Cutting Planes Proofs of Concise Pigeonhole Principles

We prove several results concerning the communication complexity of a collision-finding problem, each of which has applications to the complexity of cutting-plane proofs, which make inferences based on integer linear inequalities.

In particular, we prove an $\Omega(n^{1-1/k} \log k \ /2^k)$ lower bound on the $k$-party number-in-hand communication complexity of ... more >>>




ISSN 1433-8092 | Imprint