scientific article; zbMATH DE number 176870
[For the entire collection see Zbl 0754.00019.] The paper is devoted to the lower bound proof methods on the size of Boolean circuits computing specific Boolean functions. In recent years a big process has been done in obtaining superpolynomial lower bounds on the monotone formula and circuit size by the following three algebraic methods: (i) method of approximation introduced by \textit{A. E. Andreev} in [Sov. Math. Dokl. 31, 530-534 (1985; Zbl 0616.94019)] and \textit{A. A. Razborov} in [Sov. Math. Dokl. 31, 354-357 (1985; Zbl 0621.94027)]. (ii) method of communication complexity by \textit{R. Raz} and \textit{A. Wigderson} [Probabilistic communication complexity of Boolean relations. In: Proc. 30th IEEE FOCS, 562-567 (1989)], and (iii) method of matrix ranks introduced by \textit{A. A. Razborov} [Combinatorica 10, No. 1, 81-93 (1990; Zbl 0717.68049)]. The author of the paper discusses the impossibility to extend these methods to yield nontrivial lower bounds for the size of circuits of formulae over a complete basis. The main contribution of the paper is the proof that the last method (iii) cannot help to get nonlinear lower bounds on Boolean circuits over the standard basis with negations.
- On the limits of gate elimination
- Submodular goal value of Boolean functions
- Computability of width of submodular partition functions
- On \(\epsilon\)-sensitive monotone computations
- Prediction from partial information and hindsight, with application to circuit lower bounds
- Local bounds for the optimal information ratio of secret sharing schemes
- Submodular containment is hard, even for networks
- Applications of matrix methods to the theory of lower bounds in computational complexity
- scientific article; zbMATH DE number 981681 (Why is no real title available?)
- On \(k\)-submodular relaxation
- scientific article; zbMATH DE number 4208009 (Why is no real title available?)
- scientific article; zbMATH DE number 4170847 (Why is no real title available?)
- scientific article; zbMATH DE number 4049557 (Why is no real title available?)
- scientific article; zbMATH DE number 66469 (Why is no real title available?)
- scientific article; zbMATH DE number 524142 (Why is no real title available?)
- On the nonnegative rank of distance matrices
- On the limits of gate elimination
- Barriers for rank methods in arithmetic complexity
- Natural proofs
- Subrank and optimal reduction of scalar multiplications to generic tensors
- On the complexity of submodular function minimisation on diamonds
- A note on matrix rigidity
- Asymptotic spectra: theory, applications, and extensions
- On convex complexity measures
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4036701)