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

Related Items (35)

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 ⋮ A combinatorial approach to complexity ⋮ On convex complexity measures ⋮ Subspace intersection graphs ⋮ On derandomized composition of Boolean functions ⋮ 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