Some combinatorial-algebraic problems from complexity theory

DOI10.1016/0012-365X(94)00115-YzbMath0824.68053OpenAlexW1992906573WikidataQ127549018 ScholiaQ127549018MaRDI QIDQ1344621

Pavel Pudlák, Vojtěch Rödl

Publication date: 13 February 1995

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0012-365x(94)00115-y

zbMATH Keywords

complexity of computationsbranching program complexity

Mathematics Subject Classification ID

Computational methods for sparse matrices (65F50) Analysis of algorithms and problem complexity (68Q25) Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20) Graph theory (including graph drawing) in computer science (68R10) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Boolean functions (06E30)

Related Items (11)

Comparison of matrix norm sparsification ⋮ Dimension-free bounds and structural results in communication complexity ⋮ On a theorem of Razborov ⋮ Matrix rigidity ⋮ Learning Complexity vs Communication Complexity ⋮ Complexity measures of sign matrices ⋮ Rigidity of a simple extended lower triangular matrix ⋮ Entropy of operators or why matrix multiplication is hard for depth-two circuits ⋮ On set intersection representations of graphs ⋮ Representing \((0,1)\)-matrices by Boolean circuits ⋮ Spectral methods for matrix rigidity with applications to size-depth trade-offs and communication complexity

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on Ramsey numbers
• A combinatorial approach to complexity
• The gap between the chromatic number of a graph and the rank of its adjacency matrix is superlinear
• Communication in bounded depth circuits
• Applications of matrix methods to the theory of lower bounds in computational complexity
• Maximum Rank of Powers of a Matrix of a Given Pattern
• Linear Circuits over $\operatorname{GF}(2)$
• A counterexample to the rank-coloring conjecture
• Modified ranks of tensors and the size of circuits
• Lower Bounds for Approximation by Nonlinear Manifolds
• Systems of distinct representatives and linear algebra

This page was built for publication: Some combinatorial-algebraic problems from complexity theory