The complexity of explicit constructions

DOI10.1007/s00224-011-9368-xzbMath1282.68178OpenAlexW2035122794MaRDI QIDQ693069

Rahul Santhanam

Publication date: 7 December 2012

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://www.pure.ed.ac.uk/ws/files/17928529/Santhanam_2010_The_Complexity_of_Explicit_Constructions.pdf

zbMATH Keywords

explicit constructionscomplexity theorypseudorandomnesscombinatorial properties

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Combinatorics in computer science (68R05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (1)

The Ehrenfeucht-Fraïssé Method and the Planted Clique Conjecture

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• NP is as easy as detecting unique solutions
• The complexity of testing whether a graph is a superconcentrator
• Intersection theorems with geometric consequences
• Hardness vs randomness
• From Erdős to algorithms
• Expected complexity of graph partitioning problems
• PRIMES is in P
• 2-source dispersers for sub-polynomial entropy and Ramsey graphs beating the Frankl-Wilson construction
• Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses
• Circuit minimization problem
• How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
• Large Cliques Elude the Metropolis Process
• Computational Complexity
• On Robust Combiners for Oblivious Transfer and Other Primitives
• Pseudorandomness and Combinatorial Constructions
• Natural proofs

This page was built for publication: The complexity of explicit constructions