Variation ranks of communication matrices and lower bounds for depth-two circuits having nearly symmetric gates with unbounded fan-in
- 1 November 1995
- journal article
- Published by Springer Nature in Theory of Computing Systems
- Vol. 28 (6), 553-564
- https://doi.org/10.1007/bf01204170
Abstract
No abstract availableThis publication has 15 references indexed in Scilit:
- Separating complexity classes related to certain input oblivious logarithmic space-bounded Turing machinesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Geometric arguments yield better bounds for threshold circuits and distributed computingPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- On interpolation by analytic functions with special properties and some weak lower bounds on the size of circuits with symmetric gatesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- On oblivious branching programs of linear lengthInformation and Computation, 1991
- Multiparty protocols and logspace-hard pseudorandom sequencesPublished by Association for Computing Machinery (ACM) ,1989
- Meanders and their applications in lower bounds argumentsJournal of Computer and System Sciences, 1988
- Algebraic methods in the theory of lower bounds for Boolean circuit complexityPublished by Association for Computing Machinery (ACM) ,1987
- Parity, circuits, and the polynomial-time hierarchyTheory of Computing Systems, 1984
- Constant Depth ReducibilitySIAM Journal on Computing, 1984
- ∑11-Formulae on finite structuresAnnals of Pure and Applied Logic, 1983