Bootstrapping results for threshold circuits ``just beyond known lower bounds

DOI10.1145/3313276.3316333MaRDI QIDQ5212745zbMATH OpenOpenAlexFDO

Authors Lijie Chen, Roei Tell

Publication date 30 January 2020

Published in Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/3313276.3316333

zbMATH Keywords

circuit complexityderandomizationthreshold circuits

Mathematics Subject Classification ID

Networks and circuits as models of computation; circuit complexity (68Q06) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Quantified derandomization of linear threshold circuits
• Amplifying lower bounds by means of self-reducibility
• scientific article; zbMATH DE number 1256716
• Size--Depth Tradeoffs for Threshold Circuits
• On \(\mathrm{TC}^{0}\) lower bounds for the permanent

Cited in

(14)

• On hitting-set generators for polynomials that vanish rarely
• Amplifying lower bounds by means of self-reducibility
• Quantified Derandomization: How to Find Water in the Ocean
• A short list of equalities induces large sign-rank
• A super-quadratic lower bound for depth four arithmetic circuits
• Quantified derandomization of linear threshold circuits
• Bounds on Threshold Gate Realizability
• Size, Depth and Energy of Threshold Circuits Computing Parity Function.
• Depth-\(d\) threshold circuits vs. depth-\((d+1)\) and-or trees
• Nearly optimal pseudorandomness from hardness
• On the minimum depth of circuits with linear number of wires encoding good codes
• A direct PRF construction from Kolmogorov complexity
• On one-way functions, the worst-case hardness of time-bounded Kolmogorov complexity, and computational depth
• Learning algorithms from circuit lower bounds

This page was built for publication: Bootstrapping results for threshold circuits ``just beyond known lower bounds

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5212745)