Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > GC0:
Reports tagged with GC0:
TR24-130 | 30th August 2024
Sabee Grewal, Vinayak Kumar

Improved Circuit Lower Bounds With Applications to Exponential Separations Between Quantum and Classical Circuits

Revisions: 1

Kumar (CCC, 2023) used a novel switching lemma to prove exponential-size lower bounds for a circuit class $GC^0$ that not only contains $AC^0$ but can---with a single gate---compute functions that require exponential-size $TC^0$ circuits. Their main result was that switching-lemma lower bounds for $AC^0$ lift to $GC^0$ with no loss ... more >>>




ISSN 1433-8092 | Imprint