Andris Ambainis

Andris Ambainis, Arturs Backurs, Kaspars Balodis, Agnis Skuskovniks, Juris Smotrovs, Madars Virza: Worst Case Analysis of Non-local Games. SOFSEM 2013: 121-132

Andris Ambainis, Arturs Backurs, Juris Smotrovs, Ronald de Wolf: Optimal quantum query bounds for almost all Boolean functions. STACS 2013: 446-453

Andris Ambainis, Janis Iraids, Juris Smotrovs: Exact quantum query complexity of EXACT and THRESHOLD. CoRR abs/1302.1235 (2013)

Andris Ambainis, Abuzer Yakaryilmaz: Superiority of exact quantum automata for promise problems. Inf. Process. Lett. 112(7): 289-291 (2012)

Andris Ambainis, Julia Kempe, Or Sattath: A quantum lovász local lemma. J. ACM 59(5): 24 (2012)

Andris Ambainis, Arturs Backurs, Kaspars Balodis, Dmitrijs Kravcenko, Raitis Ozols, Juris Smotrovs, Madars Virza: Quantum Strategies Are Better Than Classical in Almost Any XOR Game. ICALP (1) 2012: 25-37

Andris Ambainis, Janis Iraids, Dmitry Kravchenko, Madars Virza: Advantage of Quantum Strategies in Random Symmetric XOR Games. MEMICS 2012: 57-68

Andris Ambainis, Arturs Backurs, Nikolajs Nahimovs, Alexander Rivosh: Grover's Algorithm with Errors. MEMICS 2012: 180-189

Andris Ambainis: Variable time amplitude amplification and quantum algorithms for linear algebra problems. STACS 2012: 636-647

Andris Ambainis, Arturs Backurs, Nikolajs Nahimovs, Raitis Ozols, Alexander Rivosh: Search by Quantum Walks on Two-Dimensional Grid without Amplitude Amplification. TQC 2012: 87-97

Andris Ambainis: Superlinear advantage for exact quantum algorithms. CoRR abs/1211.0721 (2012)

Andris Ambainis, Andrew M. Childs, Yi-Kai Liu: Quantum Property Testing for Bounded-Degree Graphs. APPROX-RANDOM 2011: 365-376

Andris Ambainis, Loïck Magnin, Martin Roetteler, Jérémie Roland: Symmetry-Assisted Adversaries for Quantum State Generation. IEEE Conference on Computational Complexity 2011: 167-177

Scott Aaronson, Andris Ambainis: The Need for Structure in Quantum Speedups. ICS 2011: 338-352

Andris Ambainis: Quantum Finite Automata. NCMA 2011: 9-13

Andris Ambainis, Xiaoming Sun: New separation between $s(f)$ and $bs(f)$. CoRR abs/1108.3494 (2011)

Andris Ambainis, Arturs Backurs, Kaspars Balodis, Dmitry Kravchenko, Raitis Ozols, Juris Smotrovs, Madars Virza: Quantum strategies are better than classical in almost any XOR game. CoRR abs/1112.3330 (2011)

Andris Ambainis, Arturs Backurs, Nikolajs Nahimovs, Raitis Ozols, Alexander Rivosh: Search by quantum walks on two-dimensional grid without amplitude amplification. CoRR abs/1112.3337 (2011)

Andris Ambainis, Xiaoming Sun: New separation between s(f) and bs(f). Electronic Colloquium on Computational Complexity (ECCC) 18: 116 (2011)

Andris Ambainis: Quantum Search with Variable Times. Theory Comput. Syst. 47(3): 786-807 (2010)

Andris Ambainis, Andrew M. Childs, François Le Gall, Seiichiro Tani: The quantum query complexity of certification. Quantum Information & Computation 10(3&4): 181-189 (2010)

Andris Ambainis: Limits on entropic uncertainty relations. Quantum Information & Computation 10(9&10): 848-858 (2010)

Andris Ambainis, Andrew M. Childs, Ben Reichardt, Robert Spalek, Shengyu Zhang: Any AND-OR Formula of Size N Can Be Evaluated in Time N^1/2+o(1) on a Quantum Computer. SIAM J. Comput. 39(6): 2513-2530 (2010)

Andris Ambainis: A New Quantum Lower Bound Method, with an Application to a Strong Direct Product Theorem for Quantum Search. Theory of Computing 6(1): 1-25 (2010)

Andris Ambainis: New Developments in Quantum Algorithms. MFCS 2010: 1-11

Andris Ambainis, Julia Kempe, Or Sattath: A quantum lovász local lemma. STOC 2010: 151-160

Andris Ambainis, Dmitry Kravchenko, Nikolajs Nahimovs, Alexander Rivosh: Nonlocal Quantum XOR Games for Large Number of Players. TAMC 2010: 72-83

Andris Ambainis: Quantum algorithms for formula evaluation. Quantum Cryptography and Computing 2010: 115-124

Andris Ambainis: Quantum algorithms for formula evaluation. CoRR abs/1006.3651 (2010)

Andris Ambainis: New Developments in Quantum Algorithms. CoRR abs/1006.4014 (2010)

Andris Ambainis: Variable time amplitude amplification and a faster quantum algorithm for solving systems of linear equations. CoRR abs/1010.4458 (2010)

Andris Ambainis, Loïck Magnin, Martin Roetteler, Jérémie Roland: Symmetry-assisted adversaries for quantum state generation. CoRR abs/1012.2112 (2010)

Andris Ambainis, Andrew M. Childs, Yi-Kai Liu: Quantum property testing for bounded-degree graphs. CoRR abs/1012.3174 (2010)

Andris Ambainis, Loïck Magnin, Martin Roetteler, Jérémie Roland: Symmetry-assisted adversaries for quantum state generation. Electronic Colloquium on Computational Complexity (ECCC) 17: 191 (2010)

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)

Andris Ambainis, Nikolajs Nahimovs: Improved constructions of quantum automata. Theor. Comput. Sci. 410(20): 1916-1922 (2009)

Andris Ambainis, Andrew M. Childs, François Le Gall, Seiichiro Tani: The quantum query complexity of certification. CoRR abs/0903.1291 (2009)

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)

Scott Aaronson, Andris Ambainis: The Need for Structure in Quantum Speedups. CoRR abs/0911.0996 (2009)

Andris Ambainis, Julia Kempe, Or Sattath: A Quantum Lovasz Local Lemma. CoRR abs/0911.1696 (2009)

Scott Aaronson, Andris Ambainis: The Need for Structure in Quantum Speedups. Electronic Colloquium on Computational Complexity (ECCC) 16: 110 (2009)

Andris Ambainis: Probabilistic and team PFIN-type learning: General properties. J. Comput. Syst. Sci. 74(4): 457-489 (2008)

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

Andris Ambainis: Quantum Random Walks - New Method for Designing Quantum Algorithms. SOFSEM 2008: 1-4

Andris Ambainis, Alexander Rivosh: Quantum Walks with Multiple or Moving Marked Locations. SOFSEM 2008: 485-496

Andris Ambainis: Quantum search with variable times. STACS 2008: 49-61

Andris Ambainis, Nikolajs Nahimovs: Improved Constructions of Quantum Automata. TQC 2008: 47-56

Andris Ambainis: Quantum Algorithm for Element Distinctness. Encyclopedia of Algorithms 2008

Andris Ambainis: Quantum Algorithm for Search on Grids. Encyclopedia of Algorithms 2008

Andris Ambainis: Quantum Walk Algorithm for Element Distinctness. SIAM J. Comput. 37(1): 210-239 (2007)

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)

Andris Ambainis, Joseph Emerson: Quantum t-designs: t-wise Independence in the Quantum World. IEEE Conference on Computational Complexity 2007: 129-140

Andris Ambainis, Andrew M. Childs, Ben Reichardt, Robert Spalek, Shengyu Zhang: Any AND-OR Formula of Size N can be Evaluated in time N^1/2+o(1) on a Quantum Computer. FOCS 2007: 363-372

Andris Ambainis, Joseph Emerson: Quantum t-designs: t-wise independence in the quantum world. Electronic Colloquium on Computational Complexity (ECCC) 14(013) (2007)

Andris Ambainis, Leonard J. Schulman, Umesh V. Vazirani: Computing with highly mixed states. J. ACM 53(3): 507-531 (2006)

Andris Ambainis: Polynomial degree vs. quantum query complexity. J. Comput. Syst. Sci. 72(2): 220-238 (2006)

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)

Andris Ambainis, Daniel Gottesman: The minimum distance problem for two-way entanglement purification. IEEE Transactions on Information Theory 52(2): 748-753 (2006)

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

Andris Ambainis, Robert Spalek: Quantum Algorithms for Matching and Network Flows. STACS 2006: 172-183

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

Andris Ambainis, Kazuo Iwama, Akinori Kawachi, Rudy Raymond Harry Putra, Shigeru Yamashita: Improved Algorithms for Quantum Identification of Boolean Oracles. SWAT 2006: 280-291

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)

Scott Aaronson, Andris Ambainis: Quantum Search of Spatial Regions. Theory of Computing 1(1): 47-79 (2005)

Andris Ambainis, Julia Kempe, Alexander Rivosh: Coins make quantum walks faster. SODA 2005: 1099-1108

Andris Ambainis: Probabilistic and Team PFIN-type Learning: General Properties. CoRR abs/cs/0504001 (2005)

Andris Ambainis: Quantum search algorithms. CoRR abs/quant-ph/0504012 (2005)

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)

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)

Andris Ambainis: A new protocol and lower bounds for quantum coin flipping. J. Comput. Syst. Sci. 68(2): 398-416 (2004)

Andris Ambainis, John Case, Sanjay Jain, Mandayam Suraj: Parsimony hierarchies for inductive inference. J. Symb. Log. 69(1): 287-327 (2004)

Andris Ambainis, Yaoyun Shi: Distributed construction of quantum fingerprints. Quantum Information & Computation 4(2): 146-151 (2004)

Andris Ambainis: Quantum search algorithms. SIGACT News 35(2): 22-35 (2004)

Andris Ambainis, Adam Smith: Small Pseudo-random Families of Matrices: Derandomizing Approximate Quantum Encryption. APPROX-RANDOM 2004: 249-260

Andris Ambainis, Harry Buhrman, Yevgeniy Dodis, Hein Röhrig: Multiparty Quantum Coin Flipping. IEEE Conference on Computational Complexity 2004: 250-259

Andris Ambainis, Ke Yang: Towards the Classical Communication Complexity of Entanglement Distillation Protocols with Incomplete Information. IEEE Conference on Computational Complexity 2004: 305-319

Andris Ambainis: Quantum Walk Algorithm for Element Distinctness. FOCS 2004: 22-31

Andris Ambainis, Markus Jakobsson, Helger Lipmaa: Cryptographic Randomized Response Techniques. Public Key Cryptography 2004: 425-438

Andris Ambainis, Martin Beaudry, Marats Golovkins, Arnolds Kikusts, Mark Mercer, Denis Thérien: Algebraic Results on Quantum Automata. STACS 2004: 93-104

Andris Ambainis, Kazuo Iwama, Akinori Kawachi, Hiroyuki Masuda, Raymond H. Putra, Shigeru Yamashita: Quantum Identification of Boolean Oracles. STACS 2004: 105-116

Andris Ambainis: Quantum algorithms a decade after shor. STOC 2004: 111

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)

Andris Ambainis, William I. Gasarch, Aravind Srinivasan, Andrey Utis: Lower bounds on the Deterministic and Quantum Communication Complexity of HAM_n^a. Electronic Colloquium on Computational Complexity (ECCC)(120) (2004)

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)

Andris Ambainis, Arnolds Kikusts: Exact results for accepting probabilities of quantum automata. Theor. Comput. Sci. 295: 3-25 (2003)

Scott Aaronson, Andris Ambainis: Quantum Search of Spatial Regions. FOCS 2003: 200-209

Andris Ambainis: Polynomial Degree vs. Quantum Query Complexity. FOCS 2003: 230-239

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

Andris Ambainis, Markus Jakobsson, Helger Lipmaa: Cryptographic Randomized Response Techniques. CoRR cs.CC/0302025 (2003)

Andris Ambainis, Harry Buhrman, Yevgeniy Dodis, Hein Röhrig: Multiparty Quantum Coin Flipping. CoRR quant-ph/0304112 (2003)

Andris Ambainis: Polynomial degree vs. quantum query complexity. CoRR quant-ph/0305028 (2003)

Andris Ambainis, Ke Yang: Towards the Classical Communication Complexity of Entanglement Distillation Protocols with Incomplete Information. Electronic Colloquium on Computational Complexity (ECCC)(082) (2003)

Andris Ambainis, Markus Jakobsson, Helger Lipmaa: Cryptographic Randomized Response Techniques. IACR Cryptology ePrint Archive 2003: 27 (2003)

Andris Ambainis, Stephen A. Bloch, David L. Schweizer: Delayed Binary Search, or Playing Twenty Questions with a Procrastinator. Algorithmica 32(4): 641-651 (2002)

Andris Ambainis, Ashwin Nayak, Amnon Ta-Shma, Umesh V. Vazirani: Dense quantum coding and quantum finite automata. J. ACM 49(4): 496-511 (2002)

Andris Ambainis: Quantum Lower Bounds by Quantum Arguments. J. Comput. Syst. Sci. 64(4): 750-767 (2002)

Benjamin C. Travaglione, Michael A. Nielsen, Howard M. Wiseman, Andris Ambainis: ROM-based computation: quantum versus classical. Quantum Information & Computation 2(4): 324-332 (2002)

Andris Ambainis, John Watrous: Two-way finite automata with quantum and classical state. Theor. Comput. Sci. 287(1): 299-311 (2002)

Andris Ambainis, Adam Smith, Ke Yang: Extracting Quantum Entanglement. IEEE Conference on Computational Complexity 2002: 103-112

Andris Ambainis: On learning formulas in the limit and with assurance. Inf. Process. Lett. 77(1): 9-11 (2001)

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)

Andris Ambainis, Kalvis Apsitis, Rusins Freivalds, Carl H. Smith: Hierarchies of probabilistic and team FIN-learning. Theor. Comput. Sci. 261(1): 91-117 (2001)

Andris Ambainis: Probabilistic inductive inference: a survey. Theor. Comput. Sci. 264(1): 155-167 (2001)

Andris Ambainis, Arnolds Kikusts: Exact Results for Accepting Probabilities of Quantum Automata. MFCS 2001: 135-147

Andris Ambainis, Arnolds Kikusts, Maris Valdats: On the Class of Languages Recognizable by 1-Way Quantum Finite Automata. STACS 2001: 75-86

Andris Ambainis, Eric Bach, Ashwin Nayak, Ashvin Vishwanath, John Watrous: One-dimensional quantum walks. STOC 2001: 37-49

Dorit Aharonov, Andris Ambainis, Julia Kempe, Umesh V. Vazirani: Quantum walks on graphs. STOC 2001: 50-59

Andris Ambainis: A new protocol and lower bounds for quantum coin flipping. STOC 2001: 134-142

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)

Andris Ambainis: How rich is the structure of the intrinsic complexity of learning. Inf. Process. Lett. 75(3): 109-112 (2000)

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

Andris Ambainis, Michele Mosca, Alain Tapp, Ronald de Wolf: Private Quantum Channels. FOCS 2000: 547-553

Andris Ambainis, Satyanarayana V. Lokam: Imroved Upper Bounds on the Simultaneous Messages Complexity of the Generalized Addressing Function. LATIN 2000: 207-216

Andris Ambainis, Ronald de Wolf: Average-Case Quantum Query Complexity. STACS 2000: 133-144

Andris Ambainis: Quantum lower bounds by quantum arguments. STOC 2000: 636-643

Andris Ambainis, Leonard J. Schulman, Umesh V. Vazirani: Computing with highly mixed states (extended abstract). STOC 2000: 697-704

Andris Ambainis: Quantum lower bounds by quantum arguments. CoRR quant-ph/0002066 (2000)

Andris Ambainis, Rusins Freivalds, Carl H. Smith: Inductive Inference with Procrastination: Back to Definitions. Fundam. Inform. 40(1): 1-16 (1999)

Andris Ambainis: A Note on Quantum Black-Box Complexity of Almost all Boolean Functions. Inf. Process. Lett. 71(1): 5-7 (1999)

Andris Ambainis, Sanjay Jain, Arun Sharma: Ordinal Mind Change Complexity of Language Identification. Theor. Comput. Sci. 220(2): 323-343 (1999)

Andris Ambainis, Richard F. Bonner, Rusins Freivalds, Arnolds Kikusts: Probabilities to Accept Languages by Quantum Finite Automata. COCOON 1999: 174-183

Andris Ambainis: A Better Lower Bound for Quantum Algorithms Searching an Ordered List. FOCS 1999: 352-357

Eric Allender, Andris Ambainis, David A. Mix Barrington, Samir Datta, Huong LeThanh: Bounded Depth Arithmetic Circuits: Counting and Closure. ICALP 1999: 149-158

Andris Ambainis, Stephen A. Bloch, David L. Schweizer: Playing Twenty Questions with a Procrastinator. SODA 1999: 844-845

Andris Ambainis, Richard F. Bonner, Rusins Freivalds, Marats Golovkins, Marek Karpinski: Quantum Finite Multitape Automata. SOFSEM 1999: 340-348

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

Andris Ambainis, John Watrous: Two-way finite automata with quantum and classical states. CoRR cs.CC/9911009 (1999)

Andris Ambainis: Probabilistic Inductive Inference:a Survey. CoRR cs.LG/9902026 (1999)

Andris Ambainis: A better lower bound for quantum algorithms searching an ordered list. CoRR quant-ph/9902053 (1999)

Andris Ambainis, Richard F. Bonner, Rusins Freivalds, Arnolds Kikusts: Probabilities to accept languages by quantum finite automata. CoRR quant-ph/9904066 (1999)

Andris Ambainis, Ronald de Wolf: Average-Case Quantum Query Complexity. CoRR quant-ph/9904079 (1999)

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)

Andris Ambainis, Rusins Freivalds: 1-Way Quantum Finite Automata: Strengths, Weaknesses and Generalizations. FOCS 1998: 332-341

Andris Ambainis, Leonard J. Schulman, Amnon Ta-Shma, Umesh V. Vazirani, Avi Wigderson: The Quantum Communication Complexity of Sampling. FOCS 1998: 342-351

Andris Ambainis, David A. Mix Barrington, Huong LeThanh: On Counting AC⁰ Circuits with Negative Constants. MFCS 1998: 409-417

Andris Ambainis, Rusins Freivalds: 1-way quantum finite automata: strengths, weaknesses and generalizations. CoRR quant-ph/9802062 (1998)

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)

Andris Ambainis: A note on quantum black-box complexity of almost all Boolean functions. CoRR quant-ph/9811080 (1998)

Andris Ambainis, David A. Mix Barrington, Huong LeThanh: On Counting AC⁰ Circuits with Negative Constants. Electronic Colloquium on Computational Complexity (ECCC) 5(20) (1998)

Andris Ambainis, Kalvis Apsitis, Rusins Freivalds, William I. Gasarch, Carl H. Smith: Team Learning as a Game. ALT 1997: 2-17

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

Andris Ambainis, Sanjay Jain, Arun Sharma: Ordinal Mind Change Complexity of Language Identification. EuroCOLT 1997: 301-315

Andris Ambainis, Richard Desper, Martin Farach, Sampath Kannan: Nearly Tight Bounds on the Learnability of Evolution. FOCS 1997: 524-533

Andris Ambainis: Upper Bound on Communication Complexity of Private Information Retrieval. ICALP 1997: 401-407

Andris Ambainis, Rusins Freivalds, Marek Karpinski: Weak and Strong Recognition by 2-way Randomized Automata. RANDOM 1997: 175-185

Andris Ambainis: Communication Complexity in a 3-Computer Model. Algorithmica 16(3): 298-301 (1996)

Andris Ambainis, Rusins Freivalds: Transformations that Preserve Learnability. ALT 1996: 299-311

Andris Ambainis: Probabilistic and Team PFIN-Type Learning: General Properties. COLT 1996: 157-168

Andris Ambainis: The Complexity of Probabilistic versus Deterministic Finite Automata. ISAAC 1996: 233-238

Andris Ambainis, Rusins Freivalds, Carl H. Smith: General Inductive Inference Types Based on Linearly-Ordered Sets. STACS 1996: 243-253

Andris Ambainis: Upper Bounds on Multiparty Communication Complexity of Shifts. STACS 1996: 631-642

Andris Ambainis: Application of Kolmogorov Complexity to Inductive Inference with Limited Memory. ALT 1995: 313-318

Andris Ambainis: The power of procrastination in inductive inference: How it depends on used ordinal notations. EuroCOLT 1995: 99-111

Andris Ambainis: Optimization Problem in Inductive Inference. GOSLER Final Report 1995: 96-107

Andris Ambainis, Juris Smotrovs: Enumerable Classes of Total Recursive Functions: Complexity of Inductive Inference. AII/ALT 1994: 10-25