Circuit-size lower bounds and non-reducibility to sparse sets
- 1 October 1982
- journal article
- Published by Elsevier in Information and Control
- Vol. 55 (1-3) , 40-56
- https://doi.org/10.1016/s0019-9958(82)90382-5
Abstract
No abstract availableKeywords
This publication has 15 references indexed in Scilit:
- AlternationJournal of the ACM, 1981
- Sparse complete sets for NP: Solution of a conjecture of Berman and HartmanisPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1980
- On another Boolean matrixTheoretical Computer Science, 1980
- On Relating Time and Space to Size and DepthSIAM Journal on Computing, 1977
- On Isomorphisms and Density of $NP$ and Other Complete SetsSIAM Journal on Computing, 1977
- Shifting Graphs and Their ApplicationsJournal of the ACM, 1976
- Monotone switching circuits and boolean matrix productComputing, 1976
- The Power of Negative Thinking in Multiplying Boolean MatricesSIAM Journal on Computing, 1975
- Complexity of monotone networks for Boolean matrix productTheoretical Computer Science, 1975
- Complexity of the realization of a linear function in the class of II-circuitsMathematical Notes, 1971