Lower Bounds for Unrestricted Boolean Circuits: Open Problems
- 25 April 2018
- book chapter
- Published by Springer Nature
- p. 15-22
Abstract
No abstract availableKeywords
This publication has 15 references indexed in Scilit:
- Some ways of thinking algorithmically about impossibilityACM SIGLOG News, 2017
- A Better-Than-3n Lower Bound for the Circuit Complexity of an Explicit Function2016
- Local Reductions2015
- Improving Exhaustive Search Implies Superpolynomial Lower BoundsSIAM Journal on Computing, 2013
- Boolean Function Complexity2012
- New upper bounds on the Boolean circuit complexity of symmetric functionsInformation Processing Letters, 2010
- Characterization of all optimal networks for a simultaneous computation of AND and NORActa Informatica, 1984
- Exponential lower bounds for restricted monotone circuits1983
- On the combinational complexity of certain symmetric Boolean functionsTheory of Computing Systems, 1976
- The Synthesis of Two-Terminal Switching CircuitsBell System Technical Journal, 1949