The most important computational problem on lattices is the shortest vector problem (SVP). In this paper, we present new algorithms that improve the state-of-the-art for provable classical/quantum algorithms for SVP. ...
详细信息
The most important computational problem on lattices is the shortest vector problem (SVP). In this paper, we present new algorithms that improve the state-of-the-art for provable classical/quantum algorithms for SVP. We present the following results: (1) A new algorithm for SVP that provides a smooth tradeoff between time complexity and memory requirement. For any positive integer 4 \leq q \leq root n, our algorithm takes q13n+o(n) time and requires poly(n) \cdot q16n/q2 memory. This tradeoff, which ranges from enumeration (q = root n) to sieving (q constant), is a consequence of a new time-memory tradeoff for discrete Gaussian sampling above the smoothing parameter. (2) A quantum algorithm for SVP that runs in time 20.950n+o(n) and requires 20.5n+o(n) classical memory and poly(n) qubits. In a quantum random access memory (QRAM) model, this algorithm takes only 20.835n+o(n) time and requires a QRAM of size 20.293n+o(n), poly(n) qubits and 20.5n classical space. This improves over the previously fastest classical (which is also the fastest quantum) algorithm due to [D. Aggarwal et al., Solving the shortest vector problem in 2n time using discrete Gaussian sampling: Extended abstract, in proceedings of the Forty-Seventh annualacm on symposium on Theory of Computing (STOC), 2015, pp. 733--742] that has a time and space complexity 2n+o(n). (3) A classical algorithm for SVP that runs in time 21.669n+o(n) time and 20.5n+o(n) space. This improves over an algorithm of [Y. Chen, K. Chung, and C. Lai, Quantum Inf. Comput., 18 (2018), pp. 285--306] that has the same space complexity. The time complexity of our classical and quantum algorithms are obtained using a known upper bound on a quantity related to the lattice kissing number, which is 20.402n. We conjecture that for most lattices this quantity is a 2o(n). Assuming that this is the case, our classical algorithm runs in time 21.292n+o(n), our quantum algorithm runs in time 20.750n+o(n), and our quantum algorithm in a QRA
The proceedings contains 167 papers from the tenthannualacm-siamsymposium on discretealgorithms. Topics discussed include: call control algorithms;motion planning;Heilbronn's triangle problems;asynchronous tra...
详细信息
The proceedings contains 167 papers from the tenthannualacm-siamsymposium on discretealgorithms. Topics discussed include: call control algorithms;motion planning;Heilbronn's triangle problems;asynchronous transfer mode (ATM) networks;Voronoi diagrams;Petersen matching theorem;Steiner triangulation;Eucledian shortest path queries;Gantt charts;tree queries;collision detection;travelling salesman problems;monotone set systems;optical networks;hierarchical cooperative caching;scheduling problems;Burrows-Wheeler transforms;Janson inequalities;degree spanning tree problems;and hamming center problems.
The proceedings contains 135 papers from the conference on Fifteenth annualacm-siamsymposium on discretealgorithms. The topics discussed include: succinct ordinal trees with level-ancestor queries;compact represent...
详细信息
The proceedings contains 135 papers from the conference on Fifteenth annualacm-siamsymposium on discretealgorithms. The topics discussed include: succinct ordinal trees with level-ancestor queries;compact representation of ordered sets;tight bounds for the partial-sums problem;finding a long directed cycle;a new algorithm for normal dominance constraints and rank-maximal matchings.
The proceedings contains 84 papers from the 8th annualacm-siamsymposium on discretealgorithms. Topics discussed include: discretealgorithms;randomized algorithms;approximation algorithms;information retrieval algo...
详细信息
The proceedings contains 84 papers from the 8th annualacm-siamsymposium on discretealgorithms. Topics discussed include: discretealgorithms;randomized algorithms;approximation algorithms;information retrieval algorithms;graph theory problems;graph vertex partitioning;data structures;constraint theory, queueing theory;NP-hard and NP-complete problems;heuristic methods;computational geometry;sorting algorithms;search algorithms;linear programming and other optimization problems;and applications of discretealgorithms to scheduling problems, communication networks, finite element analysis, and computational molecular biology.
The papers in this volume were presented at the Eighteenth annualacm-siamsymposium on discretealgorithms, held January 7/9, 2007, in New Orleans, Louisiana. The symposium was jointly sponsored by the siam Activity ...
ISBN:
(纸本)9780898716245
The papers in this volume were presented at the Eighteenth annualacm-siamsymposium on discretealgorithms, held January 7/9, 2007, in New Orleans, Louisiana. The symposium was jointly sponsored by the siam Activity Group on discrete Mathematics and by SIGACT, the acm Special Interest Group on algorithms and Computation Theory.
The proceedings contain 138 papers from the proceedings of the Sixteenth annualacm-siamsymposium on discretealgorithms. The topics discussed include: lower bounds on the size of selection and rank indexes;dynamic d...
详细信息
The proceedings contain 138 papers from the proceedings of the Sixteenth annualacm-siamsymposium on discretealgorithms. The topics discussed include: lower bounds on the size of selection and rank indexes;dynamic dictionary matching and compressed suffix trees;towards a complete characterization of tries;marriage, honesty, and stability;on distance scales, embeddings, and efficient relaxations of the cut cone;approximation algorithms for low-distortion embeddings into low-dimensional spaces;approximating connectivity augmentation problems;multidimensional balanced allocations;job shop scheduling with unit processing times;the influence of search engines on preferential attachment;and online topological ordering.
The proceedings contains 79 papers from the Ninth annualacm-siamsymposium on discretealgorithms. Topics discussed include: local search heuristics;periodic scheduling problems;polynomial time approximation schemes;...
详细信息
The proceedings contains 79 papers from the Ninth annualacm-siamsymposium on discretealgorithms. Topics discussed include: local search heuristics;periodic scheduling problems;polynomial time approximation schemes;univariate polynomial greatest common divisors;Hilbert irreducibility theorem;online file caching;online throughput-competitive algorithms;kinetic binary space partitions;input/output-efficient algorithms;three-dimensional diameter problems;quickest transshipment problems;exact arithmetic;ultimate interval graph recognition algorithms;forbidden hypergraphs;directed Steiner problems;constraint satisfaction problems;maximal matching computations;multiprocessor scheduling;and noisy radio networks.
The proceedings contain 79 papers dealing with the applications and computational methods used in solving algorithms. Topics discusssed include computation theory, automata theory, combinatorial mathematics, approxima...
详细信息
ISBN:
(纸本)0898713293
The proceedings contain 79 papers dealing with the applications and computational methods used in solving algorithms. Topics discusssed include computation theory, automata theory, combinatorial mathematics, approximation theory, matrix algebra, geometry and other mathematical techniques used in the procedure.
暂无评论