scientific article; zbMATH DE number 7561744

DOI10.4230/LIPICS.CCC.2020.16MaRDI QIDQ5092465zbMATH OpenFDO

Authors Scott Aaronson, Nai-Hui Chia, Han-Hsuan Lin, Chun-Hao Wang, Ruizhe Zhang

Publication date 21 July 2022

Full work available at URL https://arxiv.org/abs/1911.01973

zbMATH Keywords

closest pairfine grained complexityquantum computingquantum fine grained reductionquantum strong exponential time hypothesis

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cites work

• 3-SAT Faster and Simpler - Unique-SAT Bounds for PPSZ Hold in General
• A new algorithm for optimal 2-constraint satisfaction and its implications
• A Randomized Algorithm for Closest-Point Queries
• A simple randomized sieve algorithm for the closest-pair problem
• An equivalence class for orthogonal vectors
• An improved exponential-time algorithm for k -SAT
• An optimal algorithm for closest-pair maintenance
• Computational Complexity
• Deterministic APSP, orthogonal vectors, and more: quickly derandomizing Razborov-Smolensky
• Euclidean minimum spanning trees and bichromatic closest pairs
• Finding orthogonal vectors in discrete structures
• Hardness of Easy Problems: Basing Hardness on Popular Conjectures such as the Strong Exponential Time Hypothesis (Invited Talk)
• scientific article; zbMATH DE number 1579275 (Why is no real title available?)
• scientific article; zbMATH DE number 3564899 (Why is no real title available?)
• scientific article; zbMATH DE number 3569833 (Why is no real title available?)
• scientific article; zbMATH DE number 1256737 (Why is no real title available?)
• scientific article; zbMATH DE number 2080987 (Why is no real title available?)
• scientific article; zbMATH DE number 7250154 (Why is no real title available?)
• Introduction to algorithms.
• More applications of the polynomial method to algorithm design
• On closest pair in Euclidean metric: monochromatic is as hard as bichromatic
• On the complexity of k-SAT
• On the complexity of circuit satisfiability
• On the complexity of closest pair via polar-pair of point-sets
• On the complexity of d-dimensional Voronoi diagrams
• PPSZ for general \(k\)-SAT -- making Hertli's analysis simpler and 3-SAT faster
• Quantum Algorithms for Element Distinctness
• Quantum algorithms for the subset-sum problem
• Quantum Arthur-Merlin games
• Quantum lower bounds for the collision and the element distinctness problems
• Quantum Walk Algorithm for Element Distinctness
• Search via Quantum Walk
• Strengths and Weaknesses of Quantum Computing
• Tight quantum bounds for computational geometry problems

Cited in

(11)

• Quantum meets fine-grained complexity: sublinear time quantum algorithms for string problems
• Algorithms and Computation
• Quantum complexity for vector domination problem
• Near-optimal quantum algorithms for string problems
• Symmetries, graph properties, and quantum speedups
• Quantum data structure for range minimum query
• Quantum speed-ups for string synchronizing sets, longest common substring, and k-mismatch matching
• Quantum algorithms for Hopcroft's problem
• Quantum speedups for polynomial-time dynamic programming algorithms
• On the quantum time complexity of divide and conquer
• QSETH strikes again: finer quantum lower bounds for lattice problem, strong simulation, hitting set problem, and more

This page was built for publication:

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