Andris Ambainis

	2009
116		Andris Ambainis, Robert Spalek, Ronald de Wolf: A New Quantum Lower Bound Method, with Applications to Direct Product Theorems and Time-Space Tradeoffs. Algorithmica 55(3): 422-461 (2009)
115		Andris Ambainis, Andrew M. Childs, François Le Gall, Seiichiro Tani: The quantum query complexity of certification CoRR abs/0903.1291: (2009)
114		Andris Ambainis, Kazuo Iwama, Masaki Nakanishi, Harumichi Nishimura, Rudy Raymond, Seiichiro Tani, Shigeru Yamashita: Average/Worst-Case Gap of Quantum Query Complexities by On-Set Size CoRR abs/0908.2468: (2009)
113		Scott Aaronson, Andris Ambainis: The Need for Structure in Quantum Speedups CoRR abs/0911.0996: (2009)
112		Andris Ambainis, Julia Kempe, Or Sattath: A Quantum Lovasz Local Lemma CoRR abs/0911.1696: (2009)
111		Andris Ambainis, Nikolajs Nahimovs: Improved constructions of quantum automata. Theor. Comput. Sci. 410(20): 1916-1922 (2009)
	2008
110		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		Andris Ambainis: Quantum Random Walks - New Method for Designing Quantum Algorithms. SOFSEM 2008: 1-4
108		Andris Ambainis, Alexander Rivosh: Quantum Walks with Multiple or Moving Marked Locations. SOFSEM 2008: 485-496
107		Andris Ambainis: Quantum search with variable times. STACS 2008: 49-61
106		Andris Ambainis, Nikolajs Nahimovs: Improved Constructions of Quantum Automata. TQC 2008: 47-56
105		Andris Ambainis: Quantum Algorithm for Element Distinctness. Encyclopedia of Algorithms 2008
104		Andris Ambainis: Quantum Algorithm for Search on Grids. Encyclopedia of Algorithms 2008
103		Andris Ambainis: Probabilistic and team PFIN-type learning: General properties. J. Comput. Syst. Sci. 74(4): 457-489 (2008)
	2007
102		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		Andris Ambainis, Joseph Emerson: Quantum t-designs: t-wise Independence in the Quantum World. IEEE Conference on Computational Complexity 2007: 129-140
100		Andris Ambainis, Joseph Emerson: Quantum t-designs: t-wise independence in the quantum world. Electronic Colloquium on Computational Complexity (ECCC) 14(013): (2007)
99		Andris Ambainis: Quantum Walk Algorithm for Element Distinctness. SIAM J. Comput. 37(1): 210-239 (2007)
98		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		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		Andris Ambainis, Robert Spalek: Quantum Algorithms for Matching and Network Flows. STACS 2006: 172-183
95		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		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		Andris Ambainis, Daniel Gottesman: The minimum distance problem for two-way entanglement purification. IEEE Transactions on Information Theory 52(2): 748-753 (2006)
92		Andris Ambainis, Leonard J. Schulman, Umesh V. Vazirani: Computing with highly mixed states. J. ACM 53(3): 507-531 (2006)
91		Andris Ambainis: Polynomial degree vs. quantum query complexity. J. Comput. Syst. Sci. 72(2): 220-238 (2006)
90		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		Andris Ambainis, Julia Kempe, Alexander Rivosh: Coins make quantum walks faster. SODA 2005: 1099-1108
88		Andris Ambainis: Probabilistic and Team PFIN-type Learning: General Properties CoRR abs/cs/0504001: (2005)
87		Andris Ambainis: Quantum search algorithms CoRR abs/quant-ph/0504012: (2005)
86		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		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		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		Scott Aaronson, Andris Ambainis: Quantum Search of Spatial Regions. Theory of Computing 1(1): 47-79 (2005)
	2004
82		Andris Ambainis, Adam Smith: Small Pseudo-random Families of Matrices: Derandomizing Approximate Quantum Encryption. APPROX-RANDOM 2004: 249-260
81		Andris Ambainis: Quantum Walk Algorithm for Element Distinctness. FOCS 2004: 22-31
80		Andris Ambainis, Harry Buhrman, Yevgeniy Dodis, Hein Röhrig: Multiparty Quantum Coin Flipping. IEEE Conference on Computational Complexity 2004: 250-259
79		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		Andris Ambainis, Markus Jakobsson, Helger Lipmaa: Cryptographic Randomized Response Techniques. Public Key Cryptography 2004: 425-438
77		Andris Ambainis, Kazuo Iwama, Akinori Kawachi, Hiroyuki Masuda, Raymond H. Putra, Shigeru Yamashita: Quantum Identification of Boolean Oracles. STACS 2004: 105-116
76		Andris Ambainis, Martin Beaudry, Marats Golovkins, Arnolds Kikusts, Mark Mercer, Denis Thérien: Algebraic Results on Quantum Automata. STACS 2004: 93-104
75		Andris Ambainis: Quantum algorithms a decade after shor. STOC 2004: 111
74		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		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		Andris Ambainis: A new protocol and lower bounds for quantum coin flipping. J. Comput. Syst. Sci. 68(2): 398-416 (2004)
71		Andris Ambainis: Quantum search algorithms. SIGACT News 35(2): 22-35 (2004)
	2003
70		Scott Aaronson, Andris Ambainis: Quantum Search of Spatial Regions. FOCS 2003: 200-209
69		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		Andris Ambainis, Markus Jakobsson, Helger Lipmaa: Cryptographic Randomized Response Techniques CoRR cs.CC/0302025: (2003)
66		Andris Ambainis, Harry Buhrman, Yevgeniy Dodis, Hein Röhrig: Multiparty Quantum Coin Flipping CoRR quant-ph/0304112: (2003)
65		Andris Ambainis: Polynomial degree vs. quantum query complexity CoRR quant-ph/0305028: (2003)
64		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		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		Andris Ambainis, Arnolds Kikusts: Exact results for accepting probabilities of quantum automata. Theor. Comput. Sci. 295: 3-25 (2003)
	2002
61		Andris Ambainis, Adam Smith, Ke Yang: Extracting Quantum Entanglement. IEEE Conference on Computational Complexity 2002: 103-112
60		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		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		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		Andris Ambainis, Arnolds Kikusts: Exact Results for Accepting Probabilities of Quantum Automata. MFCS 2001: 135-147
55		Andris Ambainis, Arnolds Kikusts, Maris Valdats: On the Class of Languages Recognizable by 1-Way Quantum Finite Automata. STACS 2001: 75-86
54		Andris Ambainis: A new protocol and lower bounds for quantum coin flipping. STOC 2001: 134-142
53		Andris Ambainis, Eric Bach, Ashwin Nayak, Ashvin Vishwanath, John Watrous: One-dimensional quantum walks. STOC 2001: 37-49
52		Dorit Aharonov, Andris Ambainis, Julia Kempe, Umesh V. Vazirani: Quantum walks on graphs. STOC 2001: 50-59
51		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		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		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		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		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		Andris Ambainis, Ronald de Wolf: Average-Case Quantum Query Complexity. STACS 2000: 133-144
42		Andris Ambainis: Quantum lower bounds by quantum arguments. STOC 2000: 636-643
41		Andris Ambainis, Leonard J. Schulman, Umesh V. Vazirani: Computing with highly mixed states (extended abstract). STOC 2000: 697-704
40		Andris Ambainis: Quantum lower bounds by quantum arguments CoRR quant-ph/0002066: (2000)
39		Andris Ambainis: How rich is the structure of the intrinsic complexity of learning. Inf. Process. Lett. 75(3): 109-112 (2000)
	1999
38		Andris Ambainis, Richard F. Bonner, Rusins Freivalds, Arnolds Kikusts: Probabilities to Accept Languages by Quantum Finite Automata. COCOON 1999: 174-183
37		Andris Ambainis: A Better Lower Bound for Quantum Algorithms Searching an Ordered List. FOCS 1999: 352-357
36		Eric Allender, Andris Ambainis, David A. Mix Barrington, Samir Datta, Huong LeThanh: Bounded Depth Arithmetic Circuits: Counting and Closure. ICALP 1999: 149-158
35		Andris Ambainis, Stephen A. Bloch, David L. Schweizer: Playing Twenty Questions with a Procrastinator. SODA 1999: 844-845
34		Andris Ambainis, Richard F. Bonner, Rusins Freivalds, Marats Golovkins, Marek Karpinski: Quantum Finite Multitape Automata. SOFSEM 1999: 340-348
33		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		Andris Ambainis, John Watrous: Two-way finite automata with quantum and classical states CoRR cs.CC/9911009: (1999)
31		Andris Ambainis: Probabilistic Inductive Inference:a Survey CoRR cs.LG/9902026: (1999)
30		Andris Ambainis: A better lower bound for quantum algorithms searching an ordered list CoRR quant-ph/9902053: (1999)
29		Andris Ambainis, Richard F. Bonner, Rusins Freivalds, Arnolds Kikusts: Probabilities to accept languages by quantum finite automata CoRR quant-ph/9904066: (1999)
28		Andris Ambainis, Ronald de Wolf: Average-Case Quantum Query Complexity CoRR quant-ph/9904079: (1999)
27		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		Andris Ambainis: A Note on Quantum Black-Box Complexity of Almost all Boolean Functions. Inf. Process. Lett. 71(1): 5-7 (1999)
24		Andris Ambainis, Sanjay Jain, Arun Sharma: Ordinal Mind Change Complexity of Language Identification. Theor. Comput. Sci. 220(2): 323-343 (1999)
	1998
23		Andris Ambainis, Rusins Freivalds: 1-Way Quantum Finite Automata: Strengths, Weaknesses and Generalizations. FOCS 1998: 332-341
22		Andris Ambainis, Leonard J. Schulman, Amnon Ta-Shma, Umesh V. Vazirani, Avi Wigderson: The Quantum Communication Complexity of Sampling. FOCS 1998: 342-351
21		Andris Ambainis, David A. Mix Barrington, Huong LeThanh: On Counting AC0 Circuits with Negative Constants. MFCS 1998: 409-417
20		Andris Ambainis, Rusins Freivalds: 1-way quantum finite automata: strengths, weaknesses and generalizations CoRR quant-ph/9802062: (1998)
19		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		Andris Ambainis: A note on quantum black-box complexity of almost all Boolean functions CoRR quant-ph/9811080: (1998)
17		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		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		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

Coauthor Index

1	Scott Aaronson	[70] [83] [113]
2	Dorit Aharonov	[52]
3	Eric Allender	[27] [36]
4	Kalvis Apsitis	[15] [16] [48]
5	Eric Bach	[53]
6	Uldis Barbans	[68]
7	David A. Mix Barrington	[17] [21] [27] [36]
8	Martin Beaudry	[76] [90]
9	Agnese Belousova	[68]
10	Aleksandrs Belovs	[68]
11	Stephen A. Bloch	[35] [60]
12	Richard F. Bonner	[29] [34] [38]
13	Harry Buhrman	[45] [49] [51] [66] [80]
14	Cristian S. Calude (Cristian Calude)	[15]
15	Andrew M. Childs	[102] [115]
16	Samir Datta	[27] [36]
17	Richard Desper	[13]
18	Yevgeniy Dodis	[66] [80]
19	Ilze Dzelme	[68]
20	Joseph Emerson	[100] [101]
21	Martin Farach-Colton (Martin Farach)	[13]
22	Girts Folkmanis	[68]
23	Rusins Freivalds	[7] [10] [11] [15] [16] [20] [23] [26] [29] [34] [38] [48] [68]
24	François Le Gall (Francois Le Gall)	[115]
25	William I. Gasarch	[16] [45] [49] [51] [73] [74] [97]
26	Marats Golovkins	[34] [76] [90]
27	Daniel Gottesman	[93]
28	Kazuo Iwama	[77] [94] [98] [110] [114]
29	Sanjay Jain	[14] [24]
30	Markus Jakobsson	[67] [78]
31	Bala Kalyanasundaram	[45] [49] [51]
32	Sampath Kannan	[13]
33	Marek Karpinski	[11] [15] [34]
34	Akinori Kawachi	[77] [94] [98]
35	Julia Kempe	[52] [89] [112]
36	Arnolds Kikusts	[29] [38] [55] [56] [62] [76] [90]
37	Tomas Larfeldt	[15]
38	Huong LeThanh	[17] [21] [27] [36]
39	Peteris Ledins	[68]
40	Helger Lipmaa	[67] [78]
41	Satyanarayana V. Lokam	[44]
42	Hiroyuki Masuda	[77]
43	Mark Mercer	[76] [90]
44	Michele Mosca	[46]
45	Nikolajs Nahimovs	[106] [111]
46	Masaki Nakanishi	[110] [114]
47	Ashwin Nayak	[19] [33] [53] [59]
48	Harumichi Nishimura	[110] [114]
49	Rihards Opmanis	[68]
50	Raymond H. Putra (Rudy Raymond Harry Putra)	[77] [94]
51	Rudy Raymond	[98] [110] [114]
52	Ben Reichardt	[102]
53	Alexander Rivosh	[89] [108]
54	Hein Röhrig	[66] [80]
55	Iveta Sala	[15]
56	Or Sattath	[112]
57	Leonard J. Schulman	[22] [41] [63] [92]
58	David L. Schweizer	[35] [60]
59	Arun Sharma	[14] [24]
60	Agnis Skuskovniks	[68]
61	Adam Smith	[61] [82]
62	Carl H. Smith	[7] [16] [26] [48]
63	Juris Smotrovs	[1] [15]
64	Robert Spalek	[85] [95] [96] [102] [116]
65	Aravind Srinivasan	[73] [74] [97]
66	Amnon Ta-Shma	[19] [22] [33] [59] [63]
67	Seiichiro Tani	[110] [114] [115]
68	Alain Tapp	[46]
69	Denis Thérien	[76] [90]
70	Leen Torenvliet	[45] [49] [51]
71	Andrey Utis	[73] [74] [97]
72	Maris Valdats	[55]
73	Umesh V. Vazirani	[19] [22] [33] [41] [52] [59] [63] [92]
74	Ashvin Vishwanath	[53]
75	John Watrous	[32] [53] [57]
76	Avi Wigderson	[22] [63]
77	Ronald de Wolf	[28] [43] [46] [85] [95] [116]
78	Shigeru Yamashita	[77] [94] [98] [110] [114]
79	Ke Yang	[61] [64] [79]
80	Shengyu Zhang	[102]

Colors in the list of coauthors