scientific article; zbMATH DE number 7375954

DOI10.4230/LIPIcs.ICALP.2018.27zbMath1499.68386MaRDI QIDQ5002697

Manuel Sabin, Marco L. Carmosino, Russell Impagliazzo

Publication date: 28 July 2021

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

derandomizationaverage-case complexityhardness vs randomnessfine-grained complexityk-CLIQUEk-orthogonal vectors

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Randomized algorithms (68W20)

Related Items (1)

Paradigms for Unconditional Pseudorandom Generators

Cites Work

• Pseudorandom generators, typically-correct derandomization, and circuit lower bounds
• Weak derandomization of weak algorithms: explicit versions of Yao's lemma
• On the complexity of fixed parameter clique and dominating set
• \(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs
• Hardness vs randomness
• Derandomizing Arthur-Merlin games under uniform assumptions
• Randomness vs time: Derandomization under a uniform assumption
• In search of an easy witness: Exponential time vs. probabilistic polynomial time.
• Pseudorandomness and average-case complexity via uniform reductions
• A new algorithm for optimal 2-constraint satisfaction and its implications
• Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)
• Random-Self-Reducibility of Complete Sets
• How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
• Local Reductions
• Low-End Uniform Hardness versus Randomness Tradeoffs for AM
• A Pseudorandom Generator from any One-way Function
• On the Existence of Pseudorandom Generators
• Completeness for First-Order Properties on Sparse Structures with Algorithmic Applications
• Tight Hardness Results for Maximum Weight Rectangles
• Average-case fine-grained hardness
• Reducibility among Combinatorial Problems
• Consequences of Faster Alignment of Sequences
• Hardness of Easy Problems: Basing Hardness on Popular Conjectures such as the Strong Exponential Time Hypothesis (Invited Talk)
• On Worst‐Case to Average‐Case Reductions for NP Problems
• Derandomizing polynomial identity tests means proving circuit lower bounds
• Easiness assumptions and hardness tests: Trading time for zero error
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: