182 entries matching the current filters. Sorted by recently added.
Solve CVP on L 1 otimes L 2 efficiently using operatorname poly (n) calls to CVP oracles for the rank- n factors.
In polynomial time, approximate ideal-lattice SVP within operatorname poly (n) over mathbb Z[x]/(x^n+1) for power-of-two n .
Construct a classical reduction operatorname poly ( gamma,n) text -SIVP leq gamma text -GapSIVP .
Construct a dimension-preserving reduction operatorname poly ( gamma,n) text -SVP leq gamma text -SIVP .
Construct a dimension-preserving reduction gamma text -CVP leq Omega( gamma) text -GapCVP .
Approximate rank- n Euclidean shortest vector within 2^ O(n/ log n) in polynomial time.
Find a shortest nonzero vector in polynomial time from an arbitrary basis of a lattice isometric to mathbb Z^n .
Achieve time 2^ cn for rank- n exact Euclidean closest vector, with c<1 classically or c leq1/2 quantumly.
For each p geq1 , solve exact closest vector in ell p on rank- n lattices in time 2^ O(n) .
Solve exact Euclidean closest vector on rank- n lattices in time 2^ O(n) and space n^ O(1) .
Given a prime p , a generator g of mathbb F p^ and h ne0 , can a classical algorithm find x with g^x=h in time polynomial in log p ?
Can the minimum number of rotations transforming one rooted ordered binary tree into another be computed in polynomial time?
Can the winner from each vertex of a finite parity game be computed in time polynomial in the game's input size?
Is computing a canonical representative of a finite graph polynomial-time reducible to deciding graph isomorphism?
TheoremDB P3760 · algorithms
TheoremDB P3746 · algorithms
TheoremDB P9580 · Candidate awaiting source review
TheoremDB P8658 · Candidate awaiting source review
TheoremDB P9964 · Candidate awaiting source review
TheoremDB P10000 · Candidate awaiting source review
TheoremDB P3140 · theoretical computer science
TheoremDB P3764 · algorithms
TheoremDB P3726 · algorithms
TheoremDB P2600 · formal languages
TheoremDB P2560 · automata theory