The complexity of explicit constructions

DOI10.1007/S00224-011-9368-XMaRDI QIDQ693069zbMATH OpenOpenAlexFDO

Authors 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

complexity theorypseudorandomnessexplicit constructionscombinatorial properties

Mathematics Subject Classification ID

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

Recommendations

• The complexity of explicit constructions
• Pseudorandomness and Combinatorial Constructions
• scientific article; zbMATH DE number 18979
• Extractors and pseudorandom generators
• scientific article; zbMATH DE number 1833398

Cites work

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

Cited in

(7)

• Pseudorandomness and Combinatorial Constructions
• Exact complexity: the spectral decomposition of intrinsic computation
• The Ehrenfeucht-Fraïssé method and the planted clique conjecture
• The complexity of explicit constructions
• Complexity of terms, composition, and hypersubstitution
• Explicit constructions of extractors and expanders
• On the complexity of specification morphisms

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

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