Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



LATEST > REPORTS:
RSS-Feedprevious PreviousNext next

TR22-153 | 8th November 2022
Eshan Chattopadhyay, Jyun-Jie Liao

Hardness against Linear Branching Programs and More

In a recent work, Gryaznov, Pudlák and Talebanfard (CCC '22) introduced a linear variant of read-once
branching programs, with motivations from circuit and proof complexity. Such a read-once linear branching program is
a branching program where each node is allowed to make $\mathbb{F}_2$-linear queries, and are read-once in the ... more >>>


TR22-152 | 10th November 2022
Toniann Pitassi, Morgan Shirley, Adi Shraibman

The Strength of Equality Oracles in Communication

It is well-known that randomized communication protocols are more powerful than deterministic protocols. In particular the Equality function requires $\Omega(n)$ deterministic communication complexity but has efficient randomized protocols. Previous work of Chattopadhyay, Lovett and Vinyals shows that randomized communication is strictly stronger than what can be solved by deterministic protocols ... more >>>


TR22-151 | 12th November 2022
Prashanth Amireddy, Ankit Garg, Neeraj Kayal, Chandan Saha, Bhargav Thankey

Low-depth arithmetic circuit lower bounds via shifted partials

We prove super-polynomial lower bounds for low-depth arithmetic circuits using the shifted partials measure [Gupta-Kamath-Kayal-Saptharishi, CCC 2013], [Kayal, ECCC 2012] and the affine projections of partials measure [Garg-Kayal-Saha, FOCS 2020], [Kayal-Nair-Saha, STACS 2016]. The recent breakthrough work of Limaye, Srinivasan and Tavenas [FOCS 2021] proved these lower bounds by proving ... more >>>



previous PreviousNext next


ISSN 1433-8092 | Imprint