| 2009 |
|---|
| 112 | EE | Andris Ambainis,
Andrew M. Childs,
François Le Gall,
Seiichiro Tani:
The quantum query complexity of certification
CoRR abs/0903.1291: (2009) |
| 111 | EE | Andris Ambainis,
Nikolajs Nahimovs:
Improved constructions of quantum automata.
Theor. Comput. Sci. 410(20): 1916-1922 (2009) |
| 2008 |
|---|
| 110 | EE | Andris Ambainis,
Kazuo Iwama,
Masaki Nakanishi,
Harumichi Nishimura,
Rudy Raymond,
Seiichiro Tani,
Shigeru Yamashita:
Quantum Query Complexity of Boolean Functions with Small On-Sets.
ISAAC 2008: 907-918 |
| 109 | EE | Andris Ambainis:
Quantum Random Walks - New Method for Designing Quantum Algorithms.
SOFSEM 2008: 1-4 |
| 108 | EE | Andris Ambainis,
Alexander Rivosh:
Quantum Walks with Multiple or Moving Marked Locations.
SOFSEM 2008: 485-496 |
| 107 | EE | Andris Ambainis:
Quantum search with variable times.
STACS 2008: 49-61 |
| 106 | EE | Andris Ambainis,
Nikolajs Nahimovs:
Improved Constructions of Quantum Automata.
TQC 2008: 47-56 |
| 105 | EE | Andris Ambainis:
Quantum Algorithm for Element Distinctness.
Encyclopedia of Algorithms 2008 |
| 104 | EE | Andris Ambainis:
Quantum Algorithm for Search on Grids.
Encyclopedia of Algorithms 2008 |
| 103 | EE | Andris Ambainis:
Probabilistic and team PFIN-type learning: General properties.
J. Comput. Syst. Sci. 74(4): 457-489 (2008) |
| 2007 |
|---|
| 102 | EE | Andris Ambainis,
Andrew M. Childs,
Ben Reichardt,
Robert Spalek,
Shengyu Zhang:
Any AND-OR Formula of Size N can be Evaluated in time N1/2+o(1) on a Quantum Computer.
FOCS 2007: 363-372 |
| 101 | EE | Andris Ambainis,
Joseph Emerson:
Quantum t-designs: t-wise Independence in the Quantum World.
IEEE Conference on Computational Complexity 2007: 129-140 |
| 100 | EE | Andris Ambainis,
Joseph Emerson:
Quantum t-designs: t-wise independence in the quantum world.
Electronic Colloquium on Computational Complexity (ECCC) 14(013): (2007) |
| 99 | EE | Andris Ambainis:
Quantum Walk Algorithm for Element Distinctness.
SIAM J. Comput. 37(1): 210-239 (2007) |
| 98 | EE | Andris Ambainis,
Kazuo Iwama,
Akinori Kawachi,
Rudy Raymond,
Shigeru Yamashita:
Improved algorithms for quantum identification of Boolean oracles.
Theor. Comput. Sci. 378(1): 41-53 (2007) |
| 2006 |
|---|
| 97 | EE | Andris Ambainis,
William I. Gasarch,
Aravind Srinivasan,
Andrey Utis:
Lower Bounds on the Deterministic and Quantum Communication Complexities of Hamming-Distance Problems.
ISAAC 2006: 628-637 |
| 96 | EE | Andris Ambainis,
Robert Spalek:
Quantum Algorithms for Matching and Network Flows.
STACS 2006: 172-183 |
| 95 | EE | Andris Ambainis,
Robert Spalek,
Ronald de Wolf:
A new quantum lower bound method, : with applications to direct product theorems and time-space tradeoffs.
STOC 2006: 618-633 |
| 94 | EE | Andris Ambainis,
Kazuo Iwama,
Akinori Kawachi,
Rudy Raymond Harry Putra,
Shigeru Yamashita:
Improved Algorithms for Quantum Identification of Boolean Oracles.
SWAT 2006: 280-291 |
| 93 | EE | Andris Ambainis,
Daniel Gottesman:
The minimum distance problem for two-way entanglement purification.
IEEE Transactions on Information Theory 52(2): 748-753 (2006) |
| 92 | EE | Andris Ambainis,
Leonard J. Schulman,
Umesh V. Vazirani:
Computing with highly mixed states.
J. ACM 53(3): 507-531 (2006) |
| 91 | EE | Andris Ambainis:
Polynomial degree vs. quantum query complexity.
J. Comput. Syst. Sci. 72(2): 220-238 (2006) |
| 90 | EE | Andris Ambainis,
Martin Beaudry,
Marats Golovkins,
Arnolds Kikusts,
Mark Mercer,
Denis Thérien:
Algebraic Results on Quantum Automata.
Theory Comput. Syst. 39(1): 165-188 (2006) |
| 2005 |
|---|
| 89 | EE | Andris Ambainis,
Julia Kempe,
Alexander Rivosh:
Coins make quantum walks faster.
SODA 2005: 1099-1108 |
| 88 | EE | Andris Ambainis:
Probabilistic and Team PFIN-type Learning: General Properties
CoRR abs/cs/0504001: (2005) |
| 87 | EE | Andris Ambainis:
Quantum search algorithms
CoRR abs/quant-ph/0504012: (2005) |
| 86 | EE | Andris Ambainis:
A new quantum lower bound method, with an application to strong direct product theorem for quantum search
CoRR abs/quant-ph/0508200: (2005) |
| 85 | EE | Andris Ambainis,
Robert Spalek,
Ronald de Wolf:
A New Quantum Lower Bound Method, with Applications to Direct Product Theorems and Time-Space Tradeoffs
CoRR abs/quant-ph/0511200: (2005) |
| 84 | EE | Andris Ambainis:
Polynomial Degree and Lower Bounds in Quantum Complexity: Collision and Element Distinctness with Small Range.
Theory of Computing 1(1): 37-46 (2005) |
| 83 | EE | Scott Aaronson,
Andris Ambainis:
Quantum Search of Spatial Regions.
Theory of Computing 1(1): 47-79 (2005) |
| 2004 |
|---|
| 82 | EE | Andris Ambainis,
Adam Smith:
Small Pseudo-random Families of Matrices: Derandomizing Approximate Quantum Encryption.
APPROX-RANDOM 2004: 249-260 |
| 81 | EE | Andris Ambainis:
Quantum Walk Algorithm for Element Distinctness.
FOCS 2004: 22-31 |
| 80 | EE | Andris Ambainis,
Harry Buhrman,
Yevgeniy Dodis,
Hein Röhrig:
Multiparty Quantum Coin Flipping.
IEEE Conference on Computational Complexity 2004: 250-259 |
| 79 | EE | Andris Ambainis,
Ke Yang:
Towards the Classical Communication Complexity of Entanglement Distillation Protocols with Incomplete Information.
IEEE Conference on Computational Complexity 2004: 305-319 |
| 78 | EE | Andris Ambainis,
Markus Jakobsson,
Helger Lipmaa:
Cryptographic Randomized Response Techniques.
Public Key Cryptography 2004: 425-438 |
| 77 | EE | Andris Ambainis,
Kazuo Iwama,
Akinori Kawachi,
Hiroyuki Masuda,
Raymond H. Putra,
Shigeru Yamashita:
Quantum Identification of Boolean Oracles.
STACS 2004: 105-116 |
| 76 | EE | Andris Ambainis,
Martin Beaudry,
Marats Golovkins,
Arnolds Kikusts,
Mark Mercer,
Denis Thérien:
Algebraic Results on Quantum Automata.
STACS 2004: 93-104 |
| 75 | EE | Andris Ambainis:
Quantum algorithms a decade after shor.
STOC 2004: 111 |
| 74 | EE | Andris Ambainis,
William I. Gasarch,
Aravind Srinivasan,
Andrey Utis:
Lower bounds on the Deterministic and Quantum Communication Complexity of Hamming Distance
CoRR cs.CC/0411076: (2004) |
| 73 | EE | Andris Ambainis,
William I. Gasarch,
Aravind Srinivasan,
Andrey Utis:
Lower bounds on the Deterministic and Quantum Communication Complexity of HAMna
Electronic Colloquium on Computational Complexity (ECCC)(120): (2004) |
| 72 | EE | Andris Ambainis:
A new protocol and lower bounds for quantum coin flipping.
J. Comput. Syst. Sci. 68(2): 398-416 (2004) |
| 71 | EE | Andris Ambainis:
Quantum search algorithms.
SIGACT News 35(2): 22-35 (2004) |
| 2003 |
|---|
| 70 | EE | Scott Aaronson,
Andris Ambainis:
Quantum Search of Spatial Regions.
FOCS 2003: 200-209 |
| 69 | EE | Andris Ambainis:
Polynomial Degree vs. Quantum Query Complexity.
FOCS 2003: 230- |
| 68 | | Andris Ambainis,
Uldis Barbans,
Agnese Belousova,
Aleksandrs Belovs,
Ilze Dzelme,
Girts Folkmanis,
Rusins Freivalds,
Peteris Ledins,
Rihards Opmanis,
Agnis Skuskovniks:
Size of Quantum Versus Deterministic Finite Automata.
VLSI 2003: 303-308 |
| 67 | EE | Andris Ambainis,
Markus Jakobsson,
Helger Lipmaa:
Cryptographic Randomized Response Techniques
CoRR cs.CC/0302025: (2003) |
| 66 | EE | Andris Ambainis,
Harry Buhrman,
Yevgeniy Dodis,
Hein Röhrig:
Multiparty Quantum Coin Flipping
CoRR quant-ph/0304112: (2003) |
| 65 | EE | Andris Ambainis:
Polynomial degree vs. quantum query complexity
CoRR quant-ph/0305028: (2003) |
| 64 | EE | Andris Ambainis,
Ke Yang:
Towards the Classical Communication Complexity of Entanglement Distillation Protocols with Incomplete Information
Electronic Colloquium on Computational Complexity (ECCC)(082): (2003) |
| 63 | EE | Andris Ambainis,
Leonard J. Schulman,
Amnon Ta-Shma,
Umesh V. Vazirani,
Avi Wigderson:
The Quantum Communication Complexity of Sampling.
SIAM J. Comput. 32(6): 1570-1585 (2003) |
| 62 | EE | Andris Ambainis,
Arnolds Kikusts:
Exact results for accepting probabilities of quantum automata.
Theor. Comput. Sci. 295: 3-25 (2003) |
| 2002 |
|---|
| 61 | EE | Andris Ambainis,
Adam Smith,
Ke Yang:
Extracting Quantum Entanglement.
IEEE Conference on Computational Complexity 2002: 103-112 |
| 60 | EE | Andris Ambainis,
Stephen A. Bloch,
David L. Schweizer:
Delayed Binary Search, or Playing Twenty Questions with a Procrastinator.
Algorithmica 32(4): 641-651 (2002) |
| 59 | EE | Andris Ambainis,
Ashwin Nayak,
Amnon Ta-Shma,
Umesh V. Vazirani:
Dense quantum coding and quantum finite automata.
J. ACM 49(4): 496-511 (2002) |
| 58 | EE | Andris Ambainis:
Quantum Lower Bounds by Quantum Arguments.
J. Comput. Syst. Sci. 64(4): 750-767 (2002) |
| 57 | | Andris Ambainis,
John Watrous:
Two-way finite automata with quantum and classical state.
Theor. Comput. Sci. 287(1): 299-311 (2002) |
| 2001 |
|---|
| 56 | EE | Andris Ambainis,
Arnolds Kikusts:
Exact Results for Accepting Probabilities of Quantum Automata.
MFCS 2001: 135-147 |
| 55 | EE | Andris Ambainis,
Arnolds Kikusts,
Maris Valdats:
On the Class of Languages Recognizable by 1-Way Quantum Finite Automata.
STACS 2001: 75-86 |
| 54 | EE | Andris Ambainis:
A new protocol and lower bounds for quantum coin flipping.
STOC 2001: 134-142 |
| 53 | EE | Andris Ambainis,
Eric Bach,
Ashwin Nayak,
Ashvin Vishwanath,
John Watrous:
One-dimensional quantum walks.
STOC 2001: 37-49 |
| 52 | EE | Dorit Aharonov,
Andris Ambainis,
Julia Kempe,
Umesh V. Vazirani:
Quantum walks on graphs.
STOC 2001: 50-59 |
| 51 | EE | Andris Ambainis,
Harry Buhrman,
William I. Gasarch,
Bala Kalyanasundaram,
Leen Torenvliet:
The Communication Complexity of Enumeration, Elimination, and Selection
Electronic Colloquium on Computational Complexity (ECCC) 8(19): (2001) |
| 50 | EE | Andris Ambainis:
On learning formulas in the limit and with assurance.
Inf. Process. Lett. 77(1): 9-11 (2001) |
| 49 | | Andris Ambainis,
Harry Buhrman,
William I. Gasarch,
Bala Kalyanasundaram,
Leen Torenvliet:
The Communication Complexity of Enumeration, Elimination, and Selection.
J. Comput. Syst. Sci. 63(2): 148-185 (2001) |
| 48 | EE | Andris Ambainis,
Kalvis Apsitis,
Rusins Freivalds,
Carl H. Smith:
Hierarchies of probabilistic and team FIN-learning.
Theor. Comput. Sci. 261(1): 91-117 (2001) |
| 47 | EE | Andris Ambainis:
Probabilistic inductive inference: a survey.
Theor. Comput. Sci. 264(1): 155-167 (2001) |
| 2000 |
|---|
| 46 | | Andris Ambainis,
Michele Mosca,
Alain Tapp,
Ronald de Wolf:
Private Quantum Channels.
FOCS 2000: 547-553 |
| 45 | EE | Andris Ambainis,
Harry Buhrman,
William I. Gasarch,
Bala Kalyanasundaram,
Leen Torenvliet:
The Communication Complexity of Enumeration, Elimination, and Selection.
IEEE Conference on Computational Complexity 2000: 44-53 |
| 44 | | Andris Ambainis,
Satyanarayana V. Lokam:
Imroved Upper Bounds on the Simultaneous Messages Complexity of the Generalized Addressing Function.
LATIN 2000: 207-216 |
| 43 | EE | Andris Ambainis,
Ronald de Wolf:
Average-Case Quantum Query Complexity.
STACS 2000: 133-144 |
| 42 | EE | Andris Ambainis:
Quantum lower bounds by quantum arguments.
STOC 2000: 636-643 |
| 41 | EE | Andris Ambainis,
Leonard J. Schulman,
Umesh V. Vazirani:
Computing with highly mixed states (extended abstract).
STOC 2000: 697-704 |
| 40 | EE | Andris Ambainis:
Quantum lower bounds by quantum arguments
CoRR quant-ph/0002066: (2000) |
| 39 | EE | Andris Ambainis:
How rich is the structure of the intrinsic complexity of learning.
Inf. Process. Lett. 75(3): 109-112 (2000) |
| 1999 |
|---|
| 38 | EE | Andris Ambainis,
Richard F. Bonner,
Rusins Freivalds,
Arnolds Kikusts:
Probabilities to Accept Languages by Quantum Finite Automata.
COCOON 1999: 174-183 |
| 37 | EE | Andris Ambainis:
A Better Lower Bound for Quantum Algorithms Searching an Ordered List.
FOCS 1999: 352-357 |
| 36 | EE | Eric Allender,
Andris Ambainis,
David A. Mix Barrington,
Samir Datta,
Huong LeThanh:
Bounded Depth Arithmetic Circuits: Counting and Closure.
ICALP 1999: 149-158 |
| 35 | EE | Andris Ambainis,
Stephen A. Bloch,
David L. Schweizer:
Playing Twenty Questions with a Procrastinator.
SODA 1999: 844-845 |
| 34 | EE | Andris Ambainis,
Richard F. Bonner,
Rusins Freivalds,
Marats Golovkins,
Marek Karpinski:
Quantum Finite Multitape Automata.
SOFSEM 1999: 340-348 |
| 33 | EE | Andris Ambainis,
Ashwin Nayak,
Amnon Ta-Shma,
Umesh V. Vazirani:
Dense Quantum Coding and a Lower Bound for 1-Way Quantum Automata.
STOC 1999: 376-383 |
| 32 | EE | Andris Ambainis,
John Watrous:
Two-way finite automata with quantum and classical states
CoRR cs.CC/9911009: (1999) |
| 31 | EE | Andris Ambainis:
Probabilistic Inductive Inference:a Survey
CoRR cs.LG/9902026: (1999) |
| 30 | EE | Andris Ambainis:
A better lower bound for quantum algorithms searching an ordered list
CoRR quant-ph/9902053: (1999) |
| 29 | EE | Andris Ambainis,
Richard F. Bonner,
Rusins Freivalds,
Arnolds Kikusts:
Probabilities to accept languages by quantum finite automata
CoRR quant-ph/9904066: (1999) |
| 28 | EE | Andris Ambainis,
Ronald de Wolf:
Average-Case Quantum Query Complexity
CoRR quant-ph/9904079: (1999) |
| 27 | EE | Eric Allender,
Andris Ambainis,
David A. Mix Barrington,
Samir Datta,
Huong LeThanh:
Bounded Depth Arithmetic Circuits: Counting and Closure
Electronic Colloquium on Computational Complexity (ECCC) 6(12): (1999) |
| 26 | | Andris Ambainis,
Rusins Freivalds,
Carl H. Smith:
Inductive Inference with Procrastination: Back to Definitions.
Fundam. Inform. 40(1): 1-16 (1999) |
| 25 | EE | Andris Ambainis:
A Note on Quantum Black-Box Complexity of Almost all Boolean Functions.
Inf. Process. Lett. 71(1): 5-7 (1999) |
| 24 | EE | Andris Ambainis,
Sanjay Jain,
Arun Sharma:
Ordinal Mind Change Complexity of Language Identification.
Theor. Comput. Sci. 220(2): 323-343 (1999) |
| 1998 |
|---|
| 23 | EE | Andris Ambainis,
Rusins Freivalds:
1-Way Quantum Finite Automata: Strengths, Weaknesses and Generalizations.
FOCS 1998: 332-341 |
| 22 | EE | Andris Ambainis,
Leonard J. Schulman,
Amnon Ta-Shma,
Umesh V. Vazirani,
Avi Wigderson:
The Quantum Communication Complexity of Sampling.
FOCS 1998: 342-351 |
| 21 | EE | Andris Ambainis,
David A. Mix Barrington,
Huong LeThanh:
On Counting AC0 Circuits with Negative Constants.
MFCS 1998: 409-417 |
| 20 | EE | Andris Ambainis,
Rusins Freivalds:
1-way quantum finite automata: strengths, weaknesses and generalizations
CoRR quant-ph/9802062: (1998) |
| 19 | EE | Andris Ambainis,
Ashwin Nayak,
Amnon Ta-Shma,
Umesh V. Vazirani:
Dense Quantum Coding and a Lower Bound for 1-way Quantum Automata
CoRR quant-ph/9804043: (1998) |
| 18 | EE | Andris Ambainis:
A note on quantum black-box complexity of almost all Boolean functions
CoRR quant-ph/9811080: (1998) |
| 17 | EE | Andris Ambainis,
David A. Mix Barrington,
Huong LeThanh:
On Counting AC0 Circuits with Negative Constants
Electronic Colloquium on Computational Complexity (ECCC) 5(20): (1998) |
| 1997 |
|---|
| 16 | | Andris Ambainis,
Kalvis Apsitis,
Rusins Freivalds,
William I. Gasarch,
Carl H. Smith:
Team Learning as a Game.
ALT 1997: 2-17 |
| 15 | | Andris Ambainis,
Kalvis Apsitis,
Cristian Calude,
Rusins Freivalds,
Marek Karpinski,
Tomas Larfeldt,
Iveta Sala,
Juris Smotrovs:
Effects of Kolmogorov Complexity Present in Inductive Inference as Well.
ALT 1997: 244-259 |
| 14 | | Andris Ambainis,
Sanjay Jain,
Arun Sharma:
Ordinal Mind Change Complexity of Language Identification.
EuroCOLT 1997: 301-315 |
| 13 | EE | Andris Ambainis,
Richard Desper,
Martin Farach,
Sampath Kannan:
Nearly Tight Bounds on the Learnability of Evolution.
FOCS 1997: 524-533 |
| 12 | | Andris Ambainis:
Upper Bound on Communication Complexity of Private Information Retrieval.
ICALP 1997: 401-407 |
| 11 | | Andris Ambainis,
Rusins Freivalds,
Marek Karpinski:
Weak and Strong Recognition by 2-way Randomized Automata.
RANDOM 1997: 175-185 |
| 1996 |
|---|
| 10 | | Andris Ambainis,
Rusins Freivalds:
Transformations that Preserve Learnability.
ALT 1996: 299-311 |
| 9 | EE | Andris Ambainis:
Probabilistic and Team PFIN-Type Learning: General Properties.
COLT 1996: 157-168 |
| 8 | | Andris Ambainis:
The Complexity of Probabilistic versus Deterministic Finite Automata.
ISAAC 1996: 233-238 |
| 7 | | Andris Ambainis,
Rusins Freivalds,
Carl H. Smith:
General Inductive Inference Types Based on Linearly-Ordered Sets.
STACS 1996: 243-253 |
| 6 | | Andris Ambainis:
Upper Bounds on Multiparty Communication Complexity of Shifts.
STACS 1996: 631-642 |
| 5 | | Andris Ambainis:
Communication Complexity in a 3-Computer Model.
Algorithmica 16(3): 298-301 (1996) |
| 1995 |
|---|
| 4 | | Andris Ambainis:
Application of Kolmogorov Complexity to Inductive Inference with Limited Memory.
ALT 1995: 313-318 |
| 3 | | Andris Ambainis:
The power of procrastination in inductive inference: How it depends on used ordinal notations.
EuroCOLT 1995: 99-111 |
| 2 | | Andris Ambainis:
Optimization Problem in Inductive Inference.
GOSLER Final Report 1995: 96-107 |
| 1994 |
|---|
| 1 | | Andris Ambainis,
Juris Smotrovs:
Enumerable Classes of Total Recursive Functions: Complexity of Inductive Inference.
AII/ALT 1994: 10-25 |
