A combinatorial approach to complexity

DOI10.1007/BF01204724MaRDI QIDQ1196691zbMATH OpenOpenAlexFDO

Authors 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)

Cites work

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

Cited in

(11)

• Irrepresentability of short semilattices by Euclidean subspaces
• scientific article; zbMATH DE number 822063 (Why is no real title available?)
• On the intricacy of combinatorial construction problems
• The combinatorics of hidden diversity
• The complexity of combinatorial problems with succinct input representation
• Some combinatorial-algebraic problems from complexity theory
• Subspace intersection graphs
• A probabilistic analysis of a measure of combinatorial complexity for the central curve
• On the number of zero-patterns of a sequence of polynomials
• Algebraic techniques in communication complexity
• The complexity of the co-occurrence problem

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1196691)