A combinatorial approach to complexity

DOI10.1007/BF01204724zbMath0825.68483OpenAlexW1494958865MaRDI QIDQ1196691

Pavel Pudlák, Vojtěch Rödl

Publication date: 16 January 1993

Published in: Combinatorica (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Boolean functions (06E30)

Related Items (5)

Irrepresentability of short semilattices by Euclidean subspaces ⋮ Some combinatorial-algebraic problems from complexity theory ⋮ Algebraic techniques in communication complexity ⋮ On the number of zero-patterns of a sequence of polynomials ⋮ Subspace intersection graphs

Cites Work

• Probabilistic communication complexity
• Vector representations of graphs
• Embeddings of graphs in Euclidean spaces
• Geometrical embeddings of graphs
• Applications of matrix methods to the theory of lower bounds in computational complexity
• On the Shannon capacity of a graph
• Lower Bounds for Approximation by Nonlinear Manifolds

This page was built for publication: A combinatorial approach to complexity