Applications of matrix methods to the theory of lower bounds in computational complexity
One of the hardest tasks of the complexity theory is to discover some combinatorial or algebraic properties of Boolean functions which would imply high complexity in interesting computing models. A contribution in this direction is made here by proving nonpolynomial lower bound on the monotone formula size for the function ``minimum cover. Nonpolynomial lower bounds for monotone complexity were already known, and so the main contribution of this paper is in the presentation of new, essential simpler methods than the previous ones for this task. Some connections between this method on one side, and communication complexity for VLSI and graph complexity on other side are also shown.
- A Combinatorial Problem in the k-Adic Number System
- Fast parallel matrix and GCD computations
- scientific article; zbMATH DE number 3532928 (Why is no real title available?)
- Monotone Circuits for Connectivity Require Super-Logarithmic Depth
- Relating monotone formula size and monotone depth of Boolean functions
- The Brauer-Manin obstruction and \(\text{Ш}[2]\)
- The gap between monotone and non-monotone circuit complexity is exponential
- The monotone circuit complexity of Boolean functions
- СУБД: The SQL language in examples and problems
- A note on monotone complexity and the rank of matrices
- On covering graphs by complete bipartite subgraphs
- A combinatorial approach to complexity
- Some combinatorial-algebraic problems from complexity theory
- Toward the KRW composition conjecture: cubic formula lower bounds via communication complexity
- On the limits of gate elimination
- Super-logarithmic depth lower bounds via the direct sum in communication complexity
- A lower bound on computational complexity given by revelation mechanisms
- Matrix rigidity
- On abelian and homomorphic secret sharing schemes
- Polystability in positive characteristic and degree lower bounds for invariant rings
- On derandomized composition of Boolean functions
- Prediction from partial information and hindsight, with application to circuit lower bounds
- The biclique covering number of grids
- Tight lower bounds for query processing on streaming and external memory data
- Local bounds for the optimal information ratio of secret sharing schemes
- Orthogonal representations over finite fields and the chromatic number of graphs
- Efficient set intersection with simulation-based security
- Toward Better Formula Lower Bounds: The Composition of a Function and a Universal Relation
- Sufficient conditions for the local repetition-freeness of minimal -schemes realizing linear Boolean functions
- The polynomial method in circuit complexity applied to algorithm design (invited talk)
- Complexity Lower Bounds using Linear Algebra
- A stronger LP bound for formula size lower bounds via clique constraints
- On the nonnegative rank of distance matrices
- Complexity of the realization of a linear Boolean function in the class of -schemes
- The succinctness of the cover modality
- Extension complexity of independent set polytopes
- Fractional coverings, greedy coverings, and rectifier networks
- Barriers for rank methods in arithmetic complexity
- Improved composition theorems for functions and relations
- On the perfectness of minimal regular partitions of the edge set of the n-dimensional cube
- Lower Bounds for DeMorgan Circuits of Bounded Negation Width
- Binary Covering Arrays and Existentially Closed Graphs
- Query complexity of sampling and small geometric partitions
- Representations of normalized formulas
- Communication complexity meets cellular automata: necessary conditions for intrinsic universality
- Game characterizations for the number of quantifiers
- Games for succinctness of regular expressions
- Relating description complexity to entropy
- A hierarchy of constant communication complexity
- Toward better depth lower bounds: a KRW-like theorem for strong composition
- From quantifier depth to quantifier number: separating structures with k variables
- Subspace intersection graphs
- Description complexity of unary structures in first-order logic with links to entropy
- Exponential lower bounds on definable fixed points
- On the complexity of hazard-free formulas
- Searching for falsified clause in random ( n)-CNFs is hard for randomized communication
- The communication complexity of the Hamming distance problem
- On convex complexity measures
This page was built for publication: Applications of matrix methods to the theory of lower bounds in computational complexity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2638784)
