Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > NUMBER IN HAND MODEL:
Reports tagged with Number in Hand model:
TR14-074 | 14th May 2014
Arkadev Chattopadhyay, Jaikumar Radhakrishnan, Atri Rudra

Topology matters in communication

We provide the first communication lower bounds that are sensitive to the network topology for computing natural and simple functions by point to point message passing protocols for the `Number in Hand' model. All previous lower bounds were either for the broadcast model or assumed full connectivity of the network. ... more >>>


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