Applications of matrix methods to the theory of lower bounds in computational complexity

DOI10.1007/BF02122698zbMath0717.68049OpenAlexW1995365759MaRDI QIDQ2638784

Alexander A. Razborov

Publication date: 1990

Published in: Combinatorica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02122698

zbMATH Keywords

Boolean functionslower boundscommunication complexitymonotone formula

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10)

Related Items (38)

Efficient set intersection with simulation-based security ⋮ Toward the KRW composition conjecture: cubic formula lower bounds via communication complexity ⋮ Tight lower bounds for query processing on streaming and external memory data ⋮ Some combinatorial-algebraic problems from complexity theory ⋮ On the limits of gate elimination ⋮ The communication complexity of the Hamming distance problem ⋮ Sufficient conditions for the local repetition-freeness of minimal π-schemes realizing linear Boolean functions ⋮ Complexity of the Realization of a Linear Boolean Function in the Class of π-Schemes ⋮ Binary Covering Arrays and Existentially Closed Graphs ⋮ Super-logarithmic depth lower bounds via the direct sum in communication complexity ⋮ On the perfectness of minimal regular partitions of the edge set of the $n$-dimensional cube ⋮ The succinctness of the cover modality ⋮ Local bounds for the optimal information ratio of secret sharing schemes ⋮ Communication complexity meets cellular automata: necessary conditions for intrinsic universality ⋮ Unnamed Item ⋮ A stronger LP bound for formula size lower bounds via clique constraints ⋮ Query Complexity of Sampling and Small Geometric Partitions ⋮ Toward Better Formula Lower Bounds: The Composition of a Function and a Universal Relation ⋮ Unnamed Item ⋮ Extension Complexity of Independent Set Polytopes ⋮ On the nonnegative rank of distance matrices ⋮ Barriers for Rank Methods in Arithmetic Complexity ⋮ Matrix rigidity ⋮ Relating description complexity to entropy ⋮ A combinatorial approach to complexity ⋮ On convex complexity measures ⋮ Subspace intersection graphs ⋮ On derandomized composition of Boolean functions ⋮ Game characterizations for the number of quantifiers ⋮ Games for succinctness of regular expressions ⋮ A note on monotone complexity and the rank of matrices ⋮ On abelian and homomorphic secret sharing schemes ⋮ Lower Bounds for DeMorgan Circuits of Bounded Negation Width ⋮ Prediction from partial information and hindsight, with application to circuit lower bounds ⋮ On covering graphs by complete bipartite subgraphs ⋮ Orthogonal representations over finite fields and the chromatic number of graphs ⋮ The biclique covering number of grids ⋮ Polystability in positive characteristic and degree lower bounds for invariant rings

Cites Work

• Unnamed Item
• Unnamed Item
• The monotone circuit complexity of Boolean functions
• The gap between monotone and non-monotone circuit complexity is exponential
• Relating monotone formula size and monotone depth of Boolean functions
• The Brauer-Manin Obstruction and III[2]
• Monotone Circuits for Connectivity Require Super-Logarithmic Depth
• Fast parallel matrix and GCD computations
• A Combinatorial Problem in the k-Adic Number System

This page was built for publication: Applications of matrix methods to the theory of lower bounds in computational complexity