The complexity of explicit constructions

DOI10.1007/S00224-011-9368-XzbMATH Open1282.68178OpenAlexW2035122794MaRDI QIDQ693069FDOQ693069

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

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

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)

Cites Work

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

Cited In (7)

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

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)