|
|
|
||
2012
A. Ambainis, A. Yakaryilmaz.
Superiority of exact quantum automata for promise problems. Information
Processing Letters 112(7): 289-291 (2012) A. Ambainis, A. W. Harrow and M. B. Hastings. "Random Tensor
Theory: Extending Random Matrix Theory to Mixtures of Random Product
States". Communications in Mathematical Physics, 310, 25-74 (2012) A. Ambainis. Variable time amplitude amplification and a
faster quantum algorithm for solving systems of linear equations. Proceedings
of STACS 2012, to appear. Also arXiv:1010.4458. 2011
A. Ambainis, A. M. Childs, Y.-K. Liu. Quantum Property
Testing for Bounded-Degree Graphs. APPROX-RANDOM 2011: 365-376 S. Aaronson,
A. Ambainis. The Need for Structure in Quantum
Speedups. ICS 2011: 338-352 A. Ambainis, L. Magnin, M. Roetteler, J. Roland. Symmetry-Assisted Adversaries for
Quantum State Generation. IEEE Conference on Computational Complexity 2011:
167-177 A. Ambainis. Quantum Finite Automata (invited talk). NCMA
2011: 9-13 A. Ambainis, X. Sun. New separation between s(f) and bs(f). Electronic
Colloquium on Computational Complexity (ECCC) 18: 116 (2011) A. Ambainis, A. Bačkurs, K. Balodis, D. Kravchenko, R. Ozols, J. Smotrovs, M. Virza: Quantum strategies are
better than classical in almost any XOR game. arXiv:1112.3330 (2011) A. Ambainis, A. Bačkurs, N. Nahimovs, R. Ozols, A. Rivosh: Search by quantum
walks on two-dimensional grid without amplitude amplification. arXiv:1112.3337 (2011) 2010
A. Ambainis. New Developments in Quantum Algorithms (invited
talk). MFCS 2010: 1-11 A. Ambainis. Quantum algorithms for formula evaluation (invited
talk) Quantum Cryptography and Computing: Theory and Implementation, Kluwer Academic Publishers. Also arXiv:1006.3651
(2010). A. Ambainis, J. Kempe, O. Sattath. "A quantum Lovász
local lemma". STOC 2010: 151-160 A. Ambainis,
D. Kravchenko, N. Nahimovs,
A. Rivosh. Nonlocal Quantum XOR Games for Large Number
of Players. TAMC 2010, pp. 72-83. A. Ambainis. A New Quantum
Lower Bound Method, with an Application to a Strong Direct Product Theorem
for Quantum Search. Theory of Computing, 6:1-25, 2010. Earlier version:
STOC’2006. A. Ambainis, A.M. Childs, F. Le Gall, and S. Tani. The quantum query complexity of certification.
Quantum Information and Computation, 10:181-189, 2010. A. Ambainis. Quantum search with variable times. Theory of
Computing Systems, 47(3): 786-807, 2010 (special issue for the best papers of
STACS'2008). A. Ambainis. Limits on entropic uncertainty relations.
Quantum Information and Computation, 10:848-858, 2010. A. Ambainis, A. Childs, B. Reichardt,
R. Spalek, S. Zhang, "Any AND-OR formula of
size N can be evaluated in time O(N^{1/2+epsilon})
on a quantum computer". 2009
A. Ambainis, R. Spalek, R. de
Wolf. A new quantum lower bound method, with applications to direct product theorems
and time-space tradeoffs. Algorithmica, 55:
422-461, 2009. Earlier version: STOC’2006. A. Ambainis, N. Nahimovs.
"Improved Constructions of Quantum Automata". Theoretical Computer
Science, 410: 1916-1922, 2009. Earlier version: TQC’2008. A. Ambainis, J. Bouda, A. Winter.
Nonmalleable encryption of quantum information. Journal of Mathematical
Physics. 50: 42106-42113, 2009. 2008
A. Ambainis, A. Rivosh: Quantum
Walks with Multiple or Moving Marked Locations. SOFSEM 2008: 485-496 A. Ambainis. Probabilistic PFIN-type learning: general
properties. Journal of Computer and System Sciences, 74: 457-489, 2008.
Earlier version: COLT’1996. A. Ambainis. Quantum random walks - new method for designing
quantum algorithms (invited talk). Proceedings of the Conference on Current
Trends in Theory and Practice of Computer Science (SOFSEM), pp.1-4, A. Ambainis,
K. Iwama, M. Nakanishi, H. Nishimura, R. Raymond,
S. Tani, S. Yamashita. Quantum Query Complexity of
Boolean Functions with Small On-Sets. Proceedings of
ISAAC’2008, pp.
907-918. A. Ambainis. Quantum Algorithm for Search on Grids.
Encyclopedia of Algorithms 2008 A. Ambainis. Quantum Algorithm for Element Distinctness.
Encyclopedia of Algorithms 2008 2007
A. Ambainis. "Quantum walk algorithm for element
distinctness". A. Ambainis, K. Iwama, A. Kawachi, R. Raymond, S. Yamashita, "Improved algorithms
for quantum identification of Boolean oracles", Theoretical Computer
Science, vol. 278 (2007), pp. 41-53. Earlier versions: quant-ph/0411204, and
SWAT'06. A. Ambainis, J. Emerson. "Quantum t-designs: t-wise
independence in the quantum world". Proceedings of Complexity'07, pages
129-140. Also quant-ph/0701126. 2006
A. Ambainis, L. Schulman, U. Vazirani.
"Quantum computing with highly mixed states". Journal of the ACM,
53(2006), pages 507-531. (Earlier versions at
STOC'2000 and quant-ph/0003136.) A. Ambainis. “Polynomial degree vs. quantum query
complexity”. Journal of Computer and System Sciences, 72 (2006), pages
220-238. (Also FOCS'03 and quant-ph/0305028.) A. Ambainis, M. Beaudry, M. Golovkins, A. Kikusts, M.
Mercer, D. Therien. "Algebraic results on
quantum automata". Theory of Computing Systems, 39(2006), pages 165-188.
Earlier version in STACS'04. Postscript. A. Ambainis, D. Gottesman.
"Two-way entanglement purification for finite block size". IEEE
Transactions on Information Theory, 52 (2006), pages 748-753. quant-ph/0310097 A. Ambainis, R. Spalek.
"Quantum algorithms for matching and network flows". Proceedings of
STACS'06, Lecture Notes in Computer Science, 3884 (2006), pages 172-183. quant-ph/0508205 A. Ambainis, W. Gasarch, A. Srinavasan, A. Utis.
"Lower bounds on the Deterministic and Quantum Communication Complexity
of Hamming Distance". Proceedings of ISAAC'06, Lecture Notes in Computer
Science, 4288 (2007), pages 628-637. Also cs.CC/0411076 2005
A. Ambainis, J. Kempe, A. Rivosh. "Coins make quantum walks faster".
Proceedings of SODA'05, pp. 1099-1108. Also quant-ph/0402107. S. Aaronson,
A. Ambainis. “Quantum search of spatial regions”,
Theory of Computing, vol. 1(2005), pages 47-79. (Also FOCS'03 and quant-ph/0303041.) A. Ambainis. “Polynomial degree and lower bounds in quantum
complexity: collision and element distinctness with small range”. Theory of
Computing, vol. 1 (2005), pages 37-46. quant-ph/0305179 2004
A. Ambainis. "A new protocol and lower bounds for
quantum coin flipping". Journal of Computer and System Sciences,
68(2004), pages 398-416. Also STOC'01 and quant-ph/0204022. A. Ambainis. "Quantum query algorithms and lower
bounds" (survey article). Proceedings of FOTFS III, Trends on Logic,
vol. 23 (2004), pp. 15-32.Postscript. A. Ambainis, M. Jakobssen, H. Lipmaa. “Cryptographic randomized response techniques”,
Proceedings of PKC'04, pages 425-438, cs.CC/0302025. A. Ambainis, Y. Shi. “Distributed constructions of quantum
fingerprints”, Quantum Information and Computation, 4(2004), pages 146-151. quant-ph/0305022 A. Ambainis, K. Yang. "Towards the Classical
Communication Complexity of Entanglement Distillation Protocols with
Incomplete Information". Proceedings of Complexity'04, pages 305-319. quant-ph/0207090. A. Ambainis, H. Buhrman, Y. Dodis, H. Rohrig.“Multiparty
quantum coin flipping”. Proceedings of Complexity'04, pages 250-259. quant-ph/0304112. A. Ambainis. "Quantum search algorithms" (survey).
SIGACT News, vol. 35 (2004), issue 2, pages 22-35. Also quant-ph/0504012. A. Ambainis, O. Regev. "A
simple proof of quantum adiabatic theorem". quant-ph/0411152 A. Ambainis, A. Smith. "Small pseudo-random families of
matrices: derandomizing approximate quantum
encryption", Proceedings of RANDOM'04, pages 249-260. Also quant-ph/0404075. A. Ambainis, K. Iwama, A. Kawachi, H. Masuda, R. Putra, S. Yamashita. "Quantum
identification of Boolean oracles". Proceedings of STACS'04, pages
105-116. quant-ph/0403056 A. Ambainis, J. Case, S. Jain, M. Suraj. "Parsimony hierarchies for inductive
inference". Journal of Symbolic Logic, 649(2004), pages
287-327. 2003
T. Brun, H. Carteret, A. Ambainis.
"Quantum random walks with decoherent
coins", Physical Review A, 67 (2003), article 032304. Also quant-ph/0210180. T. Brun, H. Carteret, A. Ambainis.
"Quantum Walks driven by many coins", Physical Review A, 67 (2003),
article 052317. Also quant-ph/0210161. T. Brun, H. Carteret, A. Ambainis.
"The quantum to classical transition for random walks", Physical
Review Letters, 51 (2003), article 130602. quant-ph/0208195. A. Ambainis. "Quantum walks and their algorithmic
applications". International Journal of Quantum
Information, 1(2003), pages 507-518. quant-ph/0403120 A. Ambainis,
L. Schulman, A. Ta-Shma,
U. Vazirani, A. Wigderson.
"Quantum
communication complexity of sampling". Journal version,
SIAM Journal on Computing, 32(2003):1570-1585. (Earlier version: FOCS'98.) A. Ambainis, A. Kikusts.
"Exact results for accepting probabilities of quantum automata".
Theoretical Computer Science, 295(2003), pages 3-25. (Earlier versions:
MFCS'01 and quant-ph/0109136.) 2002
A. Ambainis. "Quantum lower bounds by quantum
arguments". Journal of Computer and System Sciences, 64(2002), pages 750-767.
Postcript of journal version (Earlier versions at
STOC'2000 and quant-ph/0002066.) A. Ambainis, A. Nayak, A. Ta-Shma, U. Vazirani. "Quantum dense coding and quantum finite automata". Journal of ACM, 49
(2002), pages 496-511. (Earlier versions: STOC'99 and quant-ph/9804043.) A. Ambainis, A. Smith, K. Yang. "Extracting Quantum
Entanglement (General Entanglement Purification Protocols)". Proceedings
of Complexity'2002, pages 103-112. Earlier version at quant-ph/0110010. A. Ambainis, J. Watrous.
"Two-way finite automata with quantum and classical states".
Theoretical Computer Science, 287 (2002), pages 299-311. Also cs.CC/9911009. B. Travaglione, M. Nielsen, H. Wiseman, A. Ambainis. "ROM-based computation: quantum versus
classical". Quantum Information and Computation, 2(2002), pages 324-332.
Also quant-ph/0109016.
A. Ambainis. "Lower bound for a class of weak quantum
coin flipping protocols". quant-ph/0204063. A.
Ambainis, S. Bloch, D. Schweizer.
"Delayed binary search, or Playing twenty questions with a
procrastinator". Algorithmica, 32(2002), pages
641-651. (Earlier version at SODA'99.) Gzipped postscript. 2001
D. Aharonov, A. Ambainis, J. Kempe, U. Vazirani.
"Quantum walks on graphs". Proceedings of STOC'01, pages 50-59. Postscript
of the conference version. Earlier version at quant-ph/0012090. A. Ambainis, E. Bach, A. Nayak, A.
Vishwanath, J. Watrous.
"One dimensional quantum walks". Proceedings of STOC'01, pages
37-49. Gzipped postscript. A. Ambainis, R. de Wolf. "Average-case quantum query
complexity". Journal of Physics A, 34(2001), page 6741-6754. (Earlier
version at STACS'2000.) Also quant-ph/9904079. A. Ambainis, A. Kikusts, M. Valdats. "On the class of languages recognizable by
1-way quantum finite automata". Proceedings of STACS'2001, Lecture Notes
in Computer Science 2010(2001), pages 75-86. Full version at quant-ph/0009004. A. Ambainis, H. Buhrman, W. Gasarch, B. Kalyanasundaram, L. Torenvliet.
"The communication complexity of enumeration, elimination, and
selection". Journal of Computer and System Sciences, 63(2001), pages
148-185. (Earlier version at Complexity'2000.) Gzipped postscript. A. Ambainis, K. Apsitis,
R. Freivalds, W. Gasarch,
C.H. Smith. "Hierarchies of probabilistic and team FIN-learning."
Theoretical Computer Science, 261(2001), pages 91-117. (Earlier version in
proceedings of ALT'97 with the title "Team learning as a game".) Gzipped postscript. A. Ambainis, "On learning
formulas in limit and with assurance". Information Processing Letters,
77(2001), pages 9-11.Postscript. A. Ambainis, "Probabilistic
inductive inference: a survey". Theretical
Computer Science, 264(2001), pages 155-167. Also available at cs.LG/9902026. 2000
A. Ambainis, M. Mosca, A. Tapp, R. de Wolf. "Private quantum channels".
Proceedings of FOCS'2000, pages 547-553. Gzipped postscript. A. Ambainis, S. V. Lokam. "Improved Upper Bounds on the Simultaneous
Messages Complexity of the Generalize Addressing Function". Proceedings
of LATIN'2000, Lecture Notes in Computer Science, 2136(2001), pages 135-147. Gzipped
postscript. A. Ambainis, "How rich is the
structure of the intrinsic complexity of learning?".
Information Processing Letters, 75(2000), pages 109-112. Postscript. A. Ambainis, K. Apsitis,
J. Smotrovs. "Team learning and quasi-closedness in inductive inference". Manuscript,
2000.Gzipped
postscript. 1999
A. Ambainis, R. Bonner, R. Freivalds,
A. Kikusts. "Probabilities to accept languages
by quantum finite automata". Proceedings of COCOON'99, Lecture Notes in
Computer Science, 1627(1999), pages 174-183. Also quant-ph/9904066. A. Ambainis. "A note on quantum black-box complexity of
almost all Boolean functions". Information Processing Letters, 71(1999),
pages 5-7. Also quant-ph/9811080.
A. Ambainis, "A better lower bound for quantum
algorithms searching an ordered list". Proceedings of FOCS'99, pages
352-357. Also quant-ph/9902053.
A. Ambainis, R. Bonner, R. Freivalds,
M. Golovkins, M. Karpinski.
"Quantum finite multitape automata".
Proceedings of SOFSEM'99, Lecture Notes in Computer Science, 1725(1999),
pages 340-348. Also quant-ph/9905026. A. Ambainis, R. Bonner, R. Freivalds, A. Kikusts.
"Probabilities to accept languages by quantum finite automata". Proceedings
of COCOON'99, Lecture Notes in Computer Science, 1627(1999), pages 174-183.
Also quant-ph/9904066. A. Ambainis, R. Freivalds,
C. H. Smith, "Inductive inference with procrastination: back to
definitions". Fundamenta Informaticae,
40(1999), pages 1-16. (Earlier version in proceedings of STACS'96 with the
title "General inductive inference types based on linearly-ordered
sets") Gzipped postscript. A. Ambainis, S. Jain and A. Sharma,
"Ordinal mind change complexity of language identification."Theoretical
Computer Science, 220(1999), pages 323-343. (Earlier version
: EuroCOLT'97). E.
Allender, A. Ambainis, D.
A.
Ambainis, W. Gasarch.
"Squares in a square: an on-line question". Manuscript, 1999. Gzipped postscript. 1998
A. Ambainis, R. Freivalds.
"1-way quantum finite automata: strengths, weaknesses and
generalizations." Proceedings of FOCS'98, pages 332-341. Full version
available at quant-ph/9802062. A.
Ambainis, D. 1997
A. Ambainis. "Upper bound
on the communication complexity of private information retrieval".
Proceedings of ICALP'97, Lecture Notes in Computer Science, 1256(1997), pages
401-407. Postscript. A. Ambainis, R. Freivalds,
M. Karpinski. "Weak and strong recognition by
2-way randomized automata". Proceedings of the Workshop on Randomization
and Approximation Methods in Computer Science (RANDOM'97), Lecture Notes in
Computer Science, 1269(1997), pages 175-185. Gzipped postscript. A.
Ambainis, R. Desper, M. Farach, S. Kannan, "Nearly
tight bounds on the learnability of
evolution". Proceedings of FOCS'97, pages 524-533. 1996
A. Ambainis. "Upper bounds
on multiparty communication complexity of shifts". Proceedings of
STACS'96, Lecture Notes in Computer Science, 1046 (1996), pages 631-642. A. Ambainis.
"Communication complexity in 3-computer model". Algorithmica,
16(1996), pages 298-301. A. Ambainis. "The complexity of
probabilistic versus deterministic finite automata". Proceedings of
ISAAC'96, Lecture Notes in Computer Science, 1178(1996), pages 233-237. Gzipped postscript. A. Ambainis, R. Freivalds,
J. Smotrovs, "Inevitable gaps between upper
and lower inductive inference complexity bounds". Proceedings of the
Conference on Information Processing and Management of Uncertainty in
Knowledge-Based Systems (IPMU'96) , pages 833-839. A. Ambainis,
R. Freivalds, "Transformations that preserve learnability". Proceedings of ALT'96, Lecture Notes
in Computer Science, 1160(1996), pages 299-311. Gzipped postscript. 1995
A. Ambainis, "Power of
procrastination in inductive inference: how it depends on used ordinal
notations". Proceedings of EuroCOLT'95, Lecture Notes in Computer
Science, 904(1995), pages 99-111. A. Ambainis, "Optimization
problem in inductive inference". In K.P.Jantke,
S. Lange (eds.) "Algorithmic Learning for Knowledge-Based Systems",
Lecture Notes in Computer Science, 961(1995), pages 96-107. A. Ambainis, "Application of Kolmogorov complexity to inductive inference with limited
memory". Proceedings of ALT'95, Lecture Notes in Computer Science, 997
(1995), pages 313- 318. Gzipped postscript. 1994
A. Ambainis, J. Smotrovs,
"Enumerable classes of total recursive functions: complexity of inductive
inference". Proceedings of AII'94, Lecture Notes in Computer Science,
872(1994), pages 10-25. |