Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Conference on Learning Theory

The query complexity of finding local minima in the lattice

Amos Beimel, Felix Geller, Eyal Kushilevitz Z

Published Jul 24, 1998• 2 citations
Publisher

Abstract

Article The query complexity of finding local minima in the lattice Share on Authors: Amos Beimel Division of Engineering & Applied Sciences, Harvard University, 40 Oxford St., Cambridge, MA Division of Engineering & Applied Sciences, Harvard University, 40 Oxford St., Cambridge, MAView Profile , Felix Geller Computer Science Department, Technion, Haifa 32000, Israel Computer Science Department, Technion, Haifa 32000, IsraelView Profile , Eyal Kushilevitz Computer Science Department, Technion, Haifa 32000, Israel Computer Science Department, Technion, Haifa 32000, IsraelView Profile Authors Info & Claims COLT' 98: Proceedings of the eleventh annual conference on Computational learning theoryJuly 1998 Pages 294–302https://doi.org/10.1145/279943.280000Online:24 July 1998Publication History 1citation200DownloadsMetricsTotal Citations1Total Downloads200Last 12 Months2Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

DOI
10.1145/279943.280000

Related papers

Complexity theory

Lane A. Hemaspaandra

We present high-level technical summaries of five recent results on the computational complexity of the shortest lattice vector problem.

ACM SIGACT News•Sep 1, 2001•12 citations

A proof of the security of quantum key distribution (extended abstract)

Eli Biham, Michel Boyer, P. Oscar Boykin +2 more

Article Free Access Share on A proof of the security of quantum key distribution (extended abstract) Authors: Eli Biham Computer Science Department, Technion, Haifa 32000, Israel Computer Science Department, Technion, Haifa 32000, IsraelView Profile , Michel Boyer DIRO, Université de Montréal, Montréal, Canada DIRO, Université de Montréal, Montréal, CanadaView Profile , P. Oscar Boykin Dept. of Electrical Engineering, UCLA, Los Angeles, CA Dept. of Electrical Engineering, UCLA, Los Angeles, CAView Profile , Tal Mor Dept. of Electrical Engineering, UCLA, Los Angeles, CA and Dept. of Electrical Engineering, College of Judea and Samaria, Ariel, Israel Dept. of Electrical Engineering, UCLA, Los Angeles, CA and Dept. of Electrical Engineering, College of Judea and Samaria, Ariel, IsraelView Profile , Vwani Roychowdhury Dept. of Electrical Engineering, College of Judea and Samaria, Ariel, Israel Dept. of Electrical Engineering, College of Judea and Samaria, Ariel, IsraelView Profile Authors Info & Claims STOC '00: Proceedings of the thirty-second annual ACM symposium on Theory of computingMay 2000 Pages 715–724https://doi.org/10.1145/335305.335406Published:01 May 2000Publication History 38citation1,057DownloadsMetricsTotal Citations38Total Downloads1,057Last 12 Months95Last 6 weeks17 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

ACM Symposium on Theory of Computing (STOC)•May 1, 2000•72 citations

The Complexity of CnA

William I. Gasarch, Georgia A. Martin

In this chapter we investigate the complexity of C for various n and A. We consider not only the query complexity of C as defined in Chapter 3, i.e., the least m such that there exists a set X for which C ∈ FQ(m,X), but also the number of queries to A itself that are required to compute C . (Note that, numerically speaking, the former complexity cannot exceed the latter.)

Birkhäuser Boston eBooks•Jan 1, 1999•0 citations

Quantum “encryption” (student paper panel)

Mark Hurwitz

Article Free Access Share on Quantum "encryption" (student paper panel) Author: Mark V. Hurwitz Space Sciences Laboratory, U.C. Berkeley, and 3L, Boalt Hall Space Sciences Laboratory, U.C. Berkeley, and 3L, Boalt HallView Profile Authors Info & Claims CFP '00: Proceedings of the tenth conference on Computers, freedom and privacy: challenging the assumptionsApril 2000 Pages 303–313https://doi.org/10.1145/332186.332304Online:01 April 2000Publication History 1citation637DownloadsMetricsTotal Citations1Total Downloads637Last 12 Months9Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Computers, Freedom and Privacy•Apr 1, 2000•2 citations

On the Quantum Query Complexity of Local Search in Two and Three Dimensions

Xiaoming Sun, Andrew Chi-Chih Yao

Algorithmica•Jan 28, 2008•7 citations

Quantum computer science

Eleanor Gilbert Rieffel

column Share on Quantum computer science: an introduction author of book: N. David Mermin's publisher: cambridge press, 2007, 236 pages Author: Eleanor Rieffel FX Palo Alto Laboratory, Silicon Valley, CA, USA FX Palo Alto Laboratory, Silicon Valley, CA, USAView Profile Authors Info & Claims ACM SIGACT NewsVolume 41Issue 3September 2010pp 39–44https://doi.org/10.1145/1855118.1855127Published:03 September 2010Publication History 0citation336DownloadsMetricsTotal Citations0Total Downloads336Last 12 Months14Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

ACM SIGACT News•Sep 3, 2010•0 citations
Article The query complexity of finding local minima in the lattice Share on Authors: Amos Beimel Division of Engineering & Applied Sciences, Harvard University, 40 Oxford St., Cambridge, MA Division of Engineering & Applied Sciences, Harvard University, 40 Oxford St., Cambridge, MAView Profile , Felix Geller Computer Science Department, Technion, Haifa 32000, Israel Computer Science Department, Technion, Haifa 32000, IsraelView Profile , Eyal Kushilevitz Computer Science Department, Technion, Haifa 32000, Israel Computer Science Department, Technion, Haifa 32000, IsraelView Profile Authors Info & Claims COLT' 98: Proceedings of the eleventh annual conference on Computational learning theoryJuly 1998 Pages 294–302https://doi.org/10.1145/279943.280000Online:24 July 1998Publication History 1citation200DownloadsMetricsTotal Citations1Total Downloads200Last 12 Months2Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access
Article Free Access Share on A proof of the security of quantum key distribution (extended abstract) Authors: Eli Biham Computer Science Department, Technion, Haifa 32000, Israel Computer Science Department, Technion, Haifa 32000, IsraelView Profile , Michel Boyer DIRO, Université de Montréal, Montréal, Canada DIRO, Université de Montréal, Montréal, CanadaView Profile , P. Oscar Boykin Dept. of Electrical Engineering, UCLA, Los Angeles, CA Dept. of Electrical Engineering, UCLA, Los Angeles, CAView Profile , Tal Mor Dept. of Electrical Engineering, UCLA, Los Angeles, CA and Dept. of Electrical Engineering, College of Judea and Samaria, Ariel, Israel Dept. of Electrical Engineering, UCLA, Los Angeles, CA and Dept. of Electrical Engineering, College of Judea and Samaria, Ariel, IsraelView Profile , Vwani Roychowdhury Dept. of Electrical Engineering, College of Judea and Samaria, Ariel, Israel Dept. of Electrical Engineering, College of Judea and Samaria, Ariel, IsraelView Profile Authors Info & Claims STOC '00: Proceedings of the thirty-second annual ACM symposium on Theory of computingMay 2000 Pages 715–724https://doi.org/10.1145/335305.335406Published:01 May 2000Publication History 38citation1,057DownloadsMetricsTotal Citations38Total Downloads1,057Last 12 Months95Last 6 weeks17 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF
Article Free Access Share on Quantum "encryption" (student paper panel) Author: Mark V. Hurwitz Space Sciences Laboratory, U.C. Berkeley, and 3L, Boalt Hall Space Sciences Laboratory, U.C. Berkeley, and 3L, Boalt HallView Profile Authors Info & Claims CFP '00: Proceedings of the tenth conference on Computers, freedom and privacy: challenging the assumptionsApril 2000 Pages 303–313https://doi.org/10.1145/332186.332304Online:01 April 2000Publication History 1citation637DownloadsMetricsTotal Citations1Total Downloads637Last 12 Months9Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF
column Share on Quantum computer science: an introduction author of book: N. David Mermin's publisher: cambridge press, 2007, 236 pages Author: Eleanor Rieffel FX Palo Alto Laboratory, Silicon Valley, CA, USA FX Palo Alto Laboratory, Silicon Valley, CA, USAView Profile Authors Info & Claims ACM SIGACT NewsVolume 41Issue 3September 2010pp 39–44https://doi.org/10.1145/1855118.1855127Published:03 September 2010Publication History 0citation336DownloadsMetricsTotal Citations0Total Downloads336Last 12 Months14Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access