Aleksandrs Belovs

Publication Activity (10 Years)

Years Active: 2003-2024
Publications (10 Years): 36

Top Topics

Query Complexity

Polynomial Hierarchy

Top Venues

Quantum Inf. Comput.

Electron. Colloquium Comput. Complex.

Publications

Aleksandrs Belovs
A Direct Reduction from the Polynomial to the Adversary Method. TQC (2024)
Vladimirs Andrejevs, Aleksandrs Belovs, Jevgenijs Vihrovs
Quantum algorithms for Hopcroft's problem. CoRR (2024)
Vladimirs Andrejevs, Aleksandrs Belovs, Jevgenijs Vihrovs
Quantum Algorithms for Hopcroft's Problem. MFCS (2024)
Jonathan Allcock, Jinge Bao, Aleksandrs Belovs, Troy Lee, Miklos Santha
On the quantum time complexity of divide and conquer. CoRR (2023)
Andris Ambainis, Aleksandrs Belovs
An Exponential Separation Between Quantum Query Complexity and the Polynomial Degree. CCC (2023)
Aleksandrs Belovs, Eric Blais
A Polynomial Lower Bound for Testing Monotonicity. SIAM J. Comput. 50 (3) (2021)
Aleksandrs Belovs, Arturo Castellanos, Francois Le Gall, Guillaume Malod, Alexander A. Sherstov
Quantum communication complexity of distribution testing. Quantum Inf. Comput. 21 (15&16) (2021)
Aleksandrs Belovs, Eric Blais, Abhinav Bommireddi
Testing convexity of functions over finite domains. SODA (2020)
Aleksandrs Belovs, Arturo Castellanos, François Le Gall, Guillaume Malod, Alexander A. Sherstov
Quantum Communication Complexity of Distribution Testing. CoRR (2020)
Srinivasan Arunachalam, Aleksandrs Belovs, Andrew M. Childs, Robin Kothari, Ansis Rosmanis, Ronald de Wolf
Quantum Coupon Collector. CoRR (2020)
Aleksandrs Belovs, Troy Lee
The quantum query complexity of composition with a relation. CoRR (2020)
Srinivasan Arunachalam, Aleksandrs Belovs, Andrew M. Childs, Robin Kothari, Ansis Rosmanis, Ronald de Wolf
Quantum Coupon Collector. TQC (2020)
Aleksandrs Belovs
Quantum Algorithms for Classical Probability Distributions. ESA (2019)
Aleksandrs Belovs
Quantum Algorithm for Distribution-Free Junta Testing. CSR (2019)
Aleksandrs Belovs
Quantum Dual Adversary for Hidden Subgroups and Beyond. UCNC (2019)
Aleksandrs Belovs, Eric Blais, Abhinav Bommireddi
Testing convexity of functions over finite domains. CoRR (2019)
Aleksandrs Belovs, Ansis Rosmanis
Quantum Lower Bounds for Tripartite Versions of the Hidden Shift and the Set Equality Problems. TQC (2018)
Aleksandrs Belovs
Adaptive Lower Bound for Testing Monotonicity on the Line. CoRR (2018)
Chris Cade, Ashley Montanaro, Aleksandrs Belovs
Time and space efficient quantum algorithms for detecting cycles and testing bipartiteness. Quantum Inf. Comput. 18 (1&2) (2018)
Aleksandrs Belovs, Ansis Rosmanis
Adversary lower bounds for the collision and the set equality problems. Quantum Inf. Comput. 18 (3&4) (2018)
Aleksandrs Belovs
Adaptive Lower Bound for Testing Monotonicity on the Line. APPROX-RANDOM (2018)
Aleksandrs Belovs, Gábor Ivanyos, Youming Qiao, Miklos Santha, Siyi Yang
On the Polynomial Parity Argument Complexity of the Combinatorial Nullstellensatz. Computational Complexity Conference (2017)
Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Troy Lee, Miklos Santha, Juris Smotrovs
Separations in Query Complexity Based on Pointer Functions. J. ACM 64 (5) (2017)
Aleksandrs Belovs, J. Andres Montoya, Abuzer Yakaryilmaz
On a Conjecture by Christian Choffrut. Int. J. Found. Comput. Sci. 28 (5) (2017)
Aleksandrs Belovs, Gábor Ivanyos, Youming Qiao, Miklos Santha, Siyi Yang
On the Polynomial Parity Argument Complexity of the Combinatorial Nullstellensatz. CoRR (2017)
Aleksandrs Belovs
Quantum Lower Bound for a Tripartite Version of the Hidden Shift Problem. CoRR (2017)
Aleksandrs Belovs, Gilles Brassard, Peter Høyer, Marc Kaplan, Sophie Laplante, Louis Salvail
Provably Secure Key Establishment Against Quantum Adversaries. TQC (2017)
Chris Cade, Ashley Montanaro, Aleksandrs Belovs
Time and Space Efficient Quantum Algorithms for Detecting Cycles and Testing Bipartiteness. CoRR (2016)
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. 23 (2016)
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. FOCS (2016)
Aleksandrs Belovs, Eric Blais
A polynomial lower bound for testing monotonicity. STOC (2016)
Andris Ambainis, Aleksandrs Belovs, Oded Regev, Ronald de Wolf
Efficient Quantum Algorithms for (Gapped) Group Testing and Junta Testing. SODA (2016)
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 (2016)
Aleksandrs Belovs, Juan Andrés Montoya, Abuzer Yakaryilmaz
Can one quantum bit separate any pair of words with zero-error? CoRR (2016)
Aleksandrs Belovs, J. Andres Montoya, Abuzer Yakaryilmaz
Looking for Pairs that Hard to Separate: A Quantum Approach. CIAA (2016)
Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Troy Lee, Miklos Santha, Juris Smotrovs
Separations in query complexity based on pointer functions. STOC (2016)
Aleksandrs Belovs, Eric Blais
Quantum Algorithm for Monotonicity Testing on the Hypercube. CoRR (2015)
Aleksandrs Belovs
Quantum Algorithms for Learning Symmetric Juntas via the Adversary Bound. Comput. Complex. 24 (2) (2015)
Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Troy Lee, Miklos Santha, Juris Smotrovs
Separations in Query Complexity Based on Pointer Functions. Electron. Colloquium Comput. Complex. 22 (2015)
Aleksandrs Belovs, Eric Blais
A Polynomial Lower Bound for Testing Monotonicity. CoRR (2015)
Aran Nayebi, Scott Aaronson, Aleksandrs Belovs, Luca Trevisan
Quantum lower bound for inverting a permutation with advice. Quantum Inf. Comput. 15 (11&12) (2015)
Aleksandrs Belovs, Eric Blais
Quantum Algorithm for Monotonicity Testing on the Hypercube. Theory Comput. 11 (2015)
Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Troy Lee, Miklos Santha, Juris Smotrovs
Separations in Query Complexity Based on Pointer Functions. CoRR (2015)
Andris Ambainis, Aleksandrs Belovs, Oded Regev, Ronald de Wolf
Efficient Quantum Algorithms for (Gapped) Group Testing and Junta Testing. CoRR (2015)
Aleksandrs Belovs
Quantum Algorithms for Learning Symmetric Juntas via Adversary Bound. Computational Complexity Conference (2014)
Aleksandrs Belovs, Ansis Rosmanis
On the Power of Non-adaptive Learning Graphs. Comput. Complex. 23 (2) (2014)
Aran Nayebi, Scott Aaronson, Aleksandrs Belovs, Luca Trevisan
Quantum lower bound for inverting a permutation with advice. Electron. Colloquium Comput. Complex. 21 (2014)
Aran Nayebi, Scott Aaronson, Aleksandrs Belovs, Luca Trevisan
Quantum lower bound for inverting a permutation with advice. CoRR (2014)
Aleksandrs Belovs, Robert Spalek
Adversary lower bound for the k-sum problem. ITCS (2013)
Aleksandrs Belovs, Ansis Rosmanis
On the Power of Non-adaptive Learning Graphs. Computational Complexity Conference (2013)
Aleksandrs Belovs, Andrew M. Childs, Stacey Jeffery, Robin Kothari, Frédéric Magniez
Time-Efficient Quantum Walks for 3-Distinctness. ICALP (1) (2013)
Aleksandrs Belovs, Robert Spalek
Adversary Lower Bound for the k-sum Problem CoRR (2012)
Aleksandrs Belovs
Span programs for functions with constant-sized 1-certificates: extended abstract. STOC (2012)
Aleksandrs Belovs
On the Power of Non-Adaptive Learning Graphs CoRR (2012)
Aleksandrs Belovs
Learning-Graph-Based Quantum Algorithm for k-Distinctness. FOCS (2012)
Aleksandrs Belovs, Ben W. Reichardt
Span Programs and Quantum Algorithms for st-Connectivity and Claw Detection. ESA (2012)
Aleksandrs Belovs
Adversary Lower Bound for Element Distinctness CoRR (2012)
Aleksandrs Belovs
Span-program-based quantum algorithm for the rank problem CoRR (2011)
Aleksandrs Belovs, Juris Smotrovs
A Criterion for Attaining the Welch Bounds with Applications for Mutually Unbiased Bases. MMICS (2008)
Aleksandrs Belovs
Some Algebraic Properties of Machine Poset of Infinite Words. RAIRO Theor. Informatics Appl. 42 (3) (2008)
Aleksandrs Belovs, Ansis Rosmanis, Juris Smotrovs
Multi-letter Reversible and Quantum Finite Automata. Developments in Language Theory (2007)
Aleksandrs Belovs
Non-intersecting Complexity. SOFSEM (2006)
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)