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
In this paper we provide improved running times and oracle complexities for approximately minimizing a submodular function. Our main result is a randomized algorithm, which given any submodular function defined on n-e...
详细信息
ISBN:
(纸本)9781611975994
In this paper we provide improved running times and oracle complexities for approximately minimizing a submodular function. Our main result is a randomized algorithm, which given any submodular function defined on n-elements with range [-1, 1], computes an epsilon-additive approximate minimizer in (O) over tilde (n/epsilon(2)) oracle evaluations with high probability. This improves over the (O) over tilde (n(5/3)/epsilon(2)) oracle evaluation algorithm of Chakrabarty et al. (STOC 2017) and the (O) over tilde (n3(/2)/epsilon(2)) oracle evaluation algorithm of Hamoudi et al. Further, we leverage a generalization of this result to obtain efficient algorithms for minimizing a broad class of nonconvex functions. For any function f with domain [0, 1](n) that satisfies partial derivative(2)f/partial derivative x(t)partial derivative x(j) of < 0 for all i not equal j and is L-Lipschitz with respect to the L-infinity-norm we give an algorithm that computes an epsilon-additive approximate minimizer with <(O)over tilde>(n . poly(L/epsilon)) function evaluation with high probability.
The efficiency of many discretealgorithms crucially depends on quantifying properties of large structured combinatorial configurations. We survey methods of analytic combinatorics that are simply based on the idea of...
详细信息
ISBN:
(纸本)9780898716245
The efficiency of many discretealgorithms crucially depends on quantifying properties of large structured combinatorial configurations. We survey methods of analytic combinatorics that are simply based on the idea of associating numbers to atomic elements that compose combinatorial structures, then examining the geometry of the resulting functions. In this way, an operational calculus of discrete structures emerges. Applications to basic algorithms, data structures, and the theory of random discrete structures are outlined.
At the core of the Robertson-Seymour theory of Graph Minors lies a powerful structure theorem which captures, for any fixed graph H, the common structural features of all the graphs not containing H as a minor [15]. A...
详细信息
ISBN:
(纸本)9781611975994
At the core of the Robertson-Seymour theory of Graph Minors lies a powerful structure theorem which captures, for any fixed graph H, the common structural features of all the graphs not containing H as a minor [15]. An important step towards this structure theorem is the Flat Wall Theorem [14], which has a lot of algorithmic applications (for example, the minor-testing and the disjoint paths problem with fixed number terminals). In this paper, we prove the directed analogue of this Flat Wall Theorem. Our result builds on the recent Directed Grid Theorem by two of the authors (Kawarabayashi and Kreutzer), and we hope that this is an important and significant step toward the directed structure theorem, as with the case for the undirected graph for the graph minor project.
Fix some p is an element of[0, 1] and a positive integer n. The discrete Bak-Sneppen model is a Markov chain on the space of zero-one sequences of length n with periodic boundary conditions. At each moment of time a m...
详细信息
Fix some p is an element of[0, 1] and a positive integer n. The discrete Bak-Sneppen model is a Markov chain on the space of zero-one sequences of length n with periodic boundary conditions. At each moment of time a minimum element (typically, zero) is chosen with equal probability, and it is then replaced alongside both its neighbours by independent Bernoulli(p) random variables. Let nu((n))(p) be the probability that an element of this sequence equals one under the stationary distribution of this Markov chain. It was shown in Barbay and Kenyon (in proceedings of the Twelfth annualacm-siamsymposium on discretealgorithms (Washington, DC, 2001), pp. 928-933, siam, Philadelphia, PA, 2001) that nu((n))(p) -> 1 as n -> infinity when p > 0.54...;the proof there is, alas, not rigorous. The complimentary fact that lim sup(n -> infinity)nu((n))(p) < 1 for p is an element of(0, p') for some p' > 0 is much harder;this was eventually shown in Meester and Znamenski (J Stat Phys 109:987-1004, 2002). The purpose of this note is to provide a rigorous proof of the result from Barbay and Kenyon (in proceedings of the Twelfth annualacm-siamsymposium on discretealgorithms (Washington, DC, 2001), pp. 928-933, siam, Philadelphia, PA, 2001), as well as to improve it, by showing that nu((n))(p) -> 1 when p > 0.45. (Our method, in fact, shows that with some finer tuning the same is true for p > 0.419533.)
The NP-hard discrete version of the Time-Cost Tradeoff Problem is considered. The first polynomial-time approximation algorithms for the problem are presented. Specifically, the problem of finding an optimal schedule ...
详细信息
The NP-hard discrete version of the Time-Cost Tradeoff Problem is considered. The first polynomial-time approximation algorithms for the problem are presented. Specifically, the problem of finding an optimal schedule for a project with a given budget that must not be overspent is considered. A polynomial time approximation algorithm is given with a performance ratio of 3/2 for projects with alternatives 0/1 or 0/2 for the duration of each activity. This algorithm is shown to be the best approximation that can be found, unless P = NP. The results are generalized to arbitrary projects by giving an approximation algorithm with a performance guarantee of (3/2)log2l+(7/2), where l is the ratio of the maximum duration to the minimum duration.
We initiate the study of the communication complexity of fair division with indivisible goods. We focus on some of the most well-studied fairness notions (envy-freeness, proportionality, and approximations thereof) an...
详细信息
ISBN:
(纸本)9781611975482
We initiate the study of the communication complexity of fair division with indivisible goods. We focus on some of the most well-studied fairness notions (envy-freeness, proportionality, and approximations thereof) and valuation classes (submodular, subadditive and unrestricted). Within these parameters, our results completely resolve whether the communication complexity of computing a fair allocation (or determining that none exist) is polynomial or exponential (in the number of goods), for every combination of fairness notion, valuation class, and number of players, for both deterministic and randomized protocols.
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.
暂无评论