Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

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

ISSN 1433-8092 | Imprint