NDLI: Lattices that admit logarithmic worst-case to average-case connection factors

Please wait, while we are loading the content...

Statistically-hiding commitment from any one-way function

Voronoi diagrams in n · 2o(√lg lg n) time

Faster integer multiplication

Smooth sensitivity and sampling in private data analysis

How to rank with few errors

On the submodularity of influence in social networks

Hardness of routing with congestion in directed graphs

Iteratively constructing preconditioners via the conjugate gradient method

Distributed computing theory: algorithms, impossibility results, models, and proofs

The condition number of a randomly perturbed matrix

Circuit lower bounds for Merlin-Arthur classes

Tight integrality gaps for Lovasz-Schrijver LP relaxations of vertex cover and max cut

Linear probing with constant independence

Limitations of VCG-based mechanisms

Interval completion with few edges

Parallel repetition: simplifications and the no-signaling case

Randomly coloring planar graphs with fewer colors than the maximum degree

Property testing in hypergraphs and the removal lemma

Exponential separations for one-way quantum communication complexity, with applications to cryptography

Playing games with approximation algorithms

Toward a general theory of quantum games

All-pairs bottleneck paths for general graphs in truly sub-cubic time

Uncertainty principles, extractors, and explicit embeddings of l2 into l1

Survivable network design with degree or order constraints

Lower bounds for randomized read/write stream algorithms

On achieving the "best of both worlds" in secure multiparty computation

Lower bounds for 2-dimensional range counting

Fourier meets möbius: fast subset convolution

The price of privacy and the limits of LP decoding

Approximation algorithms for budgeted learning problems

First to market is not everything: an analysis of preferential attachment with fitness

Polynomial flow-cut gaps and hardness of directed cut problems

On the convergence of Newton's method for monotone systems of polynomial equations

Balanced allocations: the weighted case

Interpolation of depth-3 arithmetic circuits with two multiplication gates

Rank complexity gap for Lovász-Schrijver and Sherali-Adams proof systems

Optimal suffix selection

The communication complexity of uncoupled nash equilibrium procedures

Computing crossing number in linear time

An efficient parallel repetition theorem for Arthur-Merlin games

Inapproximability of the Tutte polynomial

Testing k-wise and almost k-wise independence

Negative weights make adversaries stronger

Reordering buffers for general metric spaces

Search via quantum walk

More algorithms for all-pairs shortest paths in weighted graphs

Vertex cuts, random walks, and dimension reduction in series-parallel graphs

Approximating minimum bounded degree spanning trees to within one of optimal

Lower bounds in communication complexity based on factorization norms

Zero-knowledge from secure multiparty computation

Combinatorial complexity in O-minimal geometry

An approximation algorithm for max-min fair allocation of indivisible goods

Stability of the max-weight routing and scheduling protocol in dynamic networks and at critical loads

Balanced max 2-sat might not be the hardest

A combinatorial, primal-dual approach to semidefinite programs

Towards 3-query locally decodable codes of subexponential length

Separating $AC^{0}$ from depth-2 majority circuits

Proportional response dynamics leads to market equilibrium

Terminal backup, 3D matching, and covering cubic graphs

Low-end uniform hardness vs. randomness tradeoffs for AM

Tensor-based hardness of the shortest vector problem to within almost polynomial factors

Low-degree tests at large distances

On the impossibility of a quantum sieve algorithm for graph isomorphism

Some new results on node-capacitated packing of A-paths

Local embeddings of metric spaces

Improved approximation for directed cut problems

Constructing non-computable Julia sets

Simple deterministic approximation algorithms for counting matchings

Tight bounds for asynchronous randomized consensus

A 3-query PCP over integers

One sketch for all: fast algorithms for compressed sensing

Eisenberg-Gale markets: algorithms and structural properties

Holographic algorithms: from art to science

Verifying and decoding in constant depth

Lattices that admit logarithmic worst-case to average-case connection factors

An Õ(mn) Gomory-Hu tree construction algorithm for unweighted graphs

Sampling-based dimension reduction for subspace approximation

Degree-constrained network flows

Lattices that admit logarithmic worst-case to average-case connection factors

Content Provider	ACM Digital Library
Author	Peikert, Chris Rosen, Alon
Abstract	We exhibit an average-case problem that is as hard as finding γ(n)-approximate shortest nonzero vectors in certain n-dimensional lattices in the worst case, for γ(n) = O(√log n). The previously best known factor for any non-trivial class of lattices was γ(n) = Õ(n). Our results apply to families of lattices having special algebraic structure. Specifically, we consider lattices that correspond to ideals in the ring of integers of an algebraic number field. The worst-case problem we rely on is to find approximate shortest vectors in these lattices, under an appropriate form of preprocessing of the number field. For the connection factors γ(n) we achieve, the corresponding decision problems on ideal lattices are not known to be NP-hard; in fact, they are in P. However, the search approximation problems still appear to be very hard. Indeed, ideal lattices are well-studied objects in computational number theory, and the best known algorithms for them seem to perform no better than the best known algorithms for general lattices. To obtain the best possible connection factor, we instantiate our constructions with infinite families of number fields having constant root discriminant. Such families are known to exist and are computable, though no efficient construction is yet known. Our work motivates the search for such constructions. Even constructions of number fields having root discriminant up to $O(n^{2/3-ε})$ would yield connection factors better than Õ(n). As an additional contribution, we give reductions between various worst-case problems on ideal lattices, showing for example that the shortest vector problem is no harder than the closest vector problem. These results are analogous to previously-known reductions for general lattices.
Starting Page	478
Ending Page	487
Page Count	10
File Format	PDF
ISBN	9781595936318
DOI	10.1145/1250790.1250860
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2007-06-11
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Algebraic number theory Worst-case to average-case reductions Lattices
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in