default search action
Aleksandrs Belovs
Person information
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
2020 – today
- 2024
- [c28]Vladimirs Andrejevs, Aleksandrs Belovs, Jevgenijs Vihrovs:
Quantum Algorithms for Hopcroft's Problem. MFCS 2024: 9:1-9:16 - [c27]Aleksandrs Belovs:
A Direct Reduction from the Polynomial to the Adversary Method. TQC 2024: 11:1-11:15 - [i24]Vladimirs Andrejevs, Aleksandrs Belovs, Jevgenijs Vihrovs:
Quantum algorithms for Hopcroft's problem. CoRR abs/2405.01160 (2024) - 2023
- [c26]Andris Ambainis, Aleksandrs Belovs:
An Exponential Separation Between Quantum Query Complexity and the Polynomial Degree. CCC 2023: 24:1-24:13 - [i23]Jonathan Allcock, Jinge Bao, Aleksandrs Belovs, Troy Lee, Miklos Santha:
On the quantum time complexity of divide and conquer. CoRR abs/2311.16401 (2023) - 2021
- [j11]Aleksandrs Belovs, Arturo Castellanos, Francois Le Gall, Guillaume Malod, Alexander A. Sherstov:
Quantum communication complexity of distribution testing. Quantum Inf. Comput. 21(15&16): 1261-1273 (2021) - [j10]Aleksandrs Belovs, Eric Blais:
A Polynomial Lower Bound for Testing Monotonicity. SIAM J. Comput. 50(3) (2021) - 2020
- [c25]Aleksandrs Belovs, Eric Blais, Abhinav Bommireddi:
Testing convexity of functions over finite domains. SODA 2020: 2030-2045 - [c24]Srinivasan Arunachalam, Aleksandrs Belovs, Andrew M. Childs
, Robin Kothari
Quantum Coupon Collector. TQC 2020: 10:1-10:17 - [i22]Srinivasan Arunachalam, Aleksandrs Belovs, Andrew M. Childs, Robin Kothari, Ansis Rosmanis, Ronald de Wolf:
Quantum Coupon Collector. CoRR abs/2002.07688 (2020) - [i21]Aleksandrs Belovs, Troy Lee:
The quantum query complexity of composition with a relation. CoRR abs/2004.06439 (2020) - [i20]Aleksandrs Belovs, Arturo Castellanos, François Le Gall, Guillaume Malod, Alexander A. Sherstov:
Quantum Communication Complexity of Distribution Testing. CoRR abs/2006.14870 (2020)
2010 – 2019
- 2019
- [c23]Aleksandrs Belovs:
Quantum Algorithm for Distribution-Free Junta Testing. CSR 2019: 50-59 - [c22]Aleksandrs Belovs:
Quantum Algorithms for Classical Probability Distributions. ESA 2019: 16:1-16:11 - [c21]Aleksandrs Belovs:
Quantum Dual Adversary for Hidden Subgroups and Beyond. UCNC 2019: 30-36 - [i19]Aleksandrs Belovs, Eric Blais, Abhinav Bommireddi:
Testing convexity of functions over finite domains. CoRR abs/1908.02525 (2019) - 2018
- [j9]Chris Cade, Ashley Montanaro, Aleksandrs Belovs:
Time and space efficient quantum algorithms for detecting cycles and testing bipartiteness. Quantum Inf. Comput. 18(1&2): 18-50 (2018) - [j8]Aleksandrs Belovs, Ansis Rosmanis:
Adversary lower bounds for the collision and the set equality problems. Quantum Inf. Comput. 18(3&4): 200-224 (2018) - [c20]Aleksandrs Belovs:
Adaptive Lower Bound for Testing Monotonicity on the Line. APPROX-RANDOM 2018: 31:1-31:10 - [c19]Aleksandrs Belovs, Ansis Rosmanis:
Quantum Lower Bounds for Tripartite Versions of the Hidden Shift and the Set Equality Problems. TQC 2018: 3:1-3:15 - [i18]Aleksandrs Belovs:
Adaptive Lower Bound for Testing Monotonicity on the Line. CoRR abs/1801.08709 (2018) - 2017
- [j7]Aleksandrs Belovs, J. Andres Montoya
On a Conjecture by Christian Choffrut. Int. J. Found. Comput. Sci. 28(5): 483-502 (2017) - [j6]Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Troy Lee
Separations in Query Complexity Based on Pointer Functions. J. ACM 64(5): 32:1-32:24 (2017) - [c18]Aleksandrs Belovs, Gábor Ivanyos
On the Polynomial Parity Argument Complexity of the Combinatorial Nullstellensatz. CCC 2017: 30:1-30:24 - [c17]Aleksandrs Belovs, Gilles Brassard, Peter Høyer, Marc Kaplan, Sophie Laplante, Louis Salvail:
Provably Secure Key Establishment Against Quantum Adversaries. TQC 2017: 3:1-3:17 - [i17]Aleksandrs Belovs, Gábor Ivanyos, Youming Qiao, Miklos Santha, Siyi Yang:
On the Polynomial Parity Argument Complexity of the Combinatorial Nullstellensatz. CoRR abs/1710.08602 (2017) - [i16]Aleksandrs Belovs:
Quantum Lower Bound for a Tripartite Version of the Hidden Shift Problem. CoRR abs/1712.10194 (2017) - 2016
- [c16]Anurag Anshu, Aleksandrs Belovs, Shalev Ben-David, Mika Göös, Rahul Jain
Separations in Communication Complexity Using Cheat Sheets and Information Complexity. FOCS 2016: 555-564 - [c15]Andris Ambainis, Aleksandrs Belovs, Oded Regev, Ronald de Wolf:
Efficient Quantum Algorithms for (Gapped) Group Testing and Junta Testing. SODA 2016: 903-922 - [c14]Andris Ambainis, Kaspars Balodis
Separations in query complexity based on pointer functions. STOC 2016: 800-813 - [c13]Aleksandrs Belovs, Eric Blais:
A polynomial lower bound for testing monotonicity. STOC 2016: 1021-1032 - [c12]Aleksandrs Belovs, J. Andres Montoya
Looking for Pairs that Hard to Separate: A Quantum Approach. CIAA 2016: 213-223 - [r1]Aleksandrs Belovs:
Quantum Algorithms for Graph Connectivity. Encyclopedia of Algorithms 2016: 1671-1673 - [i15]Aleksandrs Belovs, Juan Andrés Montoya, Abuzer Yakaryilmaz:
Can one quantum bit separate any pair of words with zero-error? CoRR abs/1602.07967 (2016) - [i14]Anurag Anshu, Aleksandrs Belovs, Shalev Ben-David, Mika Göös, Rahul Jain, Robin Kothari, Troy Lee, Miklos Santha:
Separations in communication complexity using cheat sheets and information complexity. CoRR abs/1605.01142 (2016) - [i13]Chris Cade, Ashley Montanaro, Aleksandrs Belovs:
Time and Space Efficient Quantum Algorithms for Detecting Cycles and Testing Bipartiteness. CoRR abs/1610.00581 (2016) - [i12]Anurag Anshu, Aleksandrs Belovs, Shalev Ben-David, Mika Göös, Rahul Jain, Robin Kothari, Troy Lee, Miklos Santha:
Separations in communication complexity using cheat sheets and information complexity. Electron. Colloquium Comput. Complex. TR16 (2016) - 2015
- [j5]Aleksandrs Belovs:
Quantum Algorithms for Learning Symmetric Juntas via the Adversary Bound. Comput. Complex. 24(2): 255-293 (2015) - [j4]Aran Nayebi, Scott Aaronson, Aleksandrs Belovs, Luca Trevisan:
Quantum lower bound for inverting a permutation with advice. Quantum Inf. Comput. 15(11&12): 901-913 (2015) - [j3]Aleksandrs Belovs, Eric Blais:
Quantum Algorithm for Monotonicity Testing on the Hypercube. Theory Comput. 11: 403-412 (2015) - [i11]Aleksandrs Belovs, Eric Blais:
Quantum Algorithm for Monotonicity Testing on the Hypercube. CoRR abs/1503.02868 (2015) - [i10]Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Troy Lee, Miklos Santha, Juris Smotrovs:
Separations in Query Complexity Based on Pointer Functions. CoRR abs/1506.04719 (2015) - [i9]Andris Ambainis, Aleksandrs Belovs, Oded Regev, Ronald de Wolf:
Efficient Quantum Algorithms for (Gapped) Group Testing and Junta Testing. CoRR abs/1507.03126 (2015) - [i8]Aleksandrs Belovs, Eric Blais:
A Polynomial Lower Bound for Testing Monotonicity. CoRR abs/1511.05053 (2015) - [i7]Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Troy Lee, Miklos Santha, Juris Smotrovs:
Separations in Query Complexity Based on Pointer Functions. Electron. Colloquium Comput. Complex. TR15 (2015) - 2014
- [j2]Aleksandrs Belovs, Ansis Rosmanis:
On the Power of Non-adaptive Learning Graphs. Comput. Complex. 23(2): 323-354 (2014) - [c11]Aleksandrs Belovs:
Quantum Algorithms for Learning Symmetric Juntas via Adversary Bound. CCC 2014: 22-31 - [i6]Aran Nayebi, Scott Aaronson, Aleksandrs Belovs, Luca Trevisan:
Quantum lower bound for inverting a permutation with advice. CoRR abs/1408.3193 (2014) - [i5]Aran Nayebi, Scott Aaronson, Aleksandrs Belovs, Luca Trevisan:
Quantum lower bound for inverting a permutation with advice. Electron. Colloquium Comput. Complex. TR14 (2014) - 2013
- [c10]Aleksandrs Belovs, Ansis Rosmanis:
On the Power of Non-adaptive Learning Graphs. CCC 2013: 44-55 - [c9]Aleksandrs Belovs, Andrew M. Childs
Time-Efficient Quantum Walks for 3-Distinctness. ICALP (1) 2013: 105-122 - [c8]Aleksandrs Belovs, Robert Spalek:
Adversary lower bound for the k-sum problem. ITCS 2013: 323-328 - 2012
- [c7]Aleksandrs Belovs, Ben W. Reichardt:
Span Programs and Quantum Algorithms for st-Connectivity and Claw Detection. ESA 2012: 193-204 - [c6]Aleksandrs Belovs:
Learning-Graph-Based Quantum Algorithm for k-Distinctness. FOCS 2012: 207-216 - [c5]Aleksandrs Belovs:
Span programs for functions with constant-sized 1-certificates: extended abstract. STOC 2012: 77-84 - [i4]Aleksandrs Belovs:
Adversary Lower Bound for Element Distinctness. CoRR abs/1204.5074 (2012) - [i3]Aleksandrs Belovs, Robert Spalek:
Adversary Lower Bound for the k-sum Problem. CoRR abs/1206.6528 (2012) - [i2]Aleksandrs Belovs:
On the Power of Non-Adaptive Learning Graphs. CoRR abs/1210.3279 (2012) - 2011
- [i1]Aleksandrs Belovs:
Span-program-based quantum algorithm for the rank problem. CoRR abs/1103.0842 (2011)
2000 – 2009
- 2008
- [j1]Aleksandrs Belovs:
Some Algebraic Properties of Machine Poset of Infinite Words. RAIRO Theor. Informatics Appl. 42(3): 451-466 (2008) - [c4]Aleksandrs Belovs, Juris Smotrovs
A Criterion for Attaining the Welch Bounds with Applications for Mutually Unbiased Bases. MMICS 2008: 50-69 - 2007
- [c3]Aleksandrs Belovs, Ansis Rosmanis, Juris Smotrovs:
Multi-letter Reversible and Quantum Finite Automata. Developments in Language Theory 2007: 60-71 - 2006
- [c2]Aleksandrs Belovs:
Non-intersecting Complexity. SOFSEM 2006: 158-165 - 2003
- [c1]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
Coauthor Index
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from ,
, and
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and
to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from .
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2024-08-27 22:00 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: