Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > EXACT THRESHOLD CIRCUITS:
Reports tagged with exact threshold circuits:
TR24-142 | 17th September 2024
Ryan Williams

The Orthogonal Vectors Conjecture and Non-Uniform Circuit Lower Bounds

A line of work has shown how nontrivial uniform algorithms for analyzing circuits can be used to derive non-uniform circuit lower bounds. We show how the non-existence of nontrivial circuit-analysis algorithms can also imply non-uniform circuit lower bounds. Our connections yield new win-win circuit lower bounds, and suggest a potential ... more >>>




ISSN 1433-8092 | Imprint