dblp.uni-trier.dewww.uni-trier.de

Andris Ambainis Vis

List of publications from the DBLP Bibliography Server - FAQ
Coauthor Index - Ask others: ACM DL/Guide - CiteSeerX - CSB - MetaPress - Google - Bing - Yahoo

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

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

Colors in the list of coauthors

Copyright © Tue Nov 3 08:52:44 2009 by Michael Ley (ley@uni-trier.de)