Aleksandrs Belovs

70 papers A* 8A 7B 2C 2Misc 1Journal 40Unranked 9
YearRankTypeTitle / Venue / Authors
2026 J jnl
Space-Efficient Quantum Error Reduction without log Factors.
Quantum
Aleksandrs Belovs, Stacey Jeffery
2026 J jnl
Tight Quantum Lower Bound for Approximate Counting with Quantum States.
Comput. Complex.
Aleksandrs Belovs, Ansis Rosmanis
2025 J jnl
An Exponential Separation Between Quantum Query Complexity and the Polynomial Degree.
Comput. Complex.
Andris Ambainis, Aleksandrs Belovs
2025 A* conf
On the Quantum Time Complexity of Divide and Conquer.
ICALP
Jonathan Allcock, Jinge Bao, Aleksandrs Belovs, Troy Lee, Miklos Santha
2025 J jnl
Space-Efficient Quantum Error Reduction without log Factors.
CoRR
Aleksandrs Belovs, Stacey Jeffery
2024 — conf
A Direct Reduction from the Polynomial to the Adversary Method.
TQC
Aleksandrs Belovs
2024 B conf
Quantum Algorithms for Hopcroft's Problem.
MFCS
Vladimirs Andrejevs, Aleksandrs Belovs, Jevgenijs Vihrovs
2024 J jnl
Quantum algorithms for Hopcroft's problem.
CoRR
Vladimirs Andrejevs, Aleksandrs Belovs, Jevgenijs Vihrovs
2024 J jnl
Taming Quantum Time Complexity.
Quantum
Aleksandrs Belovs, Stacey Jeffery, Duyal Yolcu
2023 A conf
An Exponential Separation Between Quantum Query Complexity and the Polynomial Degree.
CCC
Andris Ambainis, Aleksandrs Belovs
2023 J jnl
On the quantum time complexity of divide and conquer.
CoRR
Jonathan Allcock, Jinge Bao, Aleksandrs Belovs, Troy Lee, Miklos Santha
2021 J jnl
A Polynomial Lower Bound for Testing Monotonicity.
SIAM J. Comput.
Aleksandrs Belovs, Eric Blais
2021 J jnl
Quantum communication complexity of distribution testing.
Quantum Inf. Comput.
Aleksandrs Belovs, Arturo Castellanos, Francois Le Gall, Guillaume Malod, Alexander A. Sherstov
2020 J jnl
Quantum Communication Complexity of Distribution Testing.
CoRR
Aleksandrs Belovs, Arturo Castellanos, François Le Gall, Guillaume Malod, Alexander A. Sherstov
2020 — conf
Quantum Coupon Collector.
TQC
Srinivasan Arunachalam, Aleksandrs Belovs, Andrew M. Childs, Robin Kothari, Ansis Rosmanis, Ronald de Wolf
2020 J jnl
Quantum Coupon Collector.
CoRR
Srinivasan Arunachalam, Aleksandrs Belovs, Andrew M. Childs, Robin Kothari, Ansis Rosmanis, Ronald de Wolf
2020 A* conf
Testing convexity of functions over finite domains.
SODA
Aleksandrs Belovs, Eric Blais, Abhinav Bommireddi
2020 J jnl
The quantum query complexity of composition with a relation.
CoRR
Aleksandrs Belovs, Troy Lee
2019 Misc conf
Quantum Algorithm for Distribution-Free Junta Testing.
CSR
Aleksandrs Belovs
2019 A conf
Quantum Algorithms for Classical Probability Distributions.
ESA
Aleksandrs Belovs
2019 — conf
Quantum Dual Adversary for Hidden Subgroups and Beyond.
UCNC
Aleksandrs Belovs
2019 J jnl
Testing convexity of functions over finite domains.
CoRR
Aleksandrs Belovs, Eric Blais, Abhinav Bommireddi
2018 — conf
Adaptive Lower Bound for Testing Monotonicity on the Line.
APPROX-RANDOM
Aleksandrs Belovs
2018 J jnl
Adaptive Lower Bound for Testing Monotonicity on the Line.
CoRR
Aleksandrs Belovs
2018 J jnl
Adversary lower bounds for the collision and the set equality problems.
Quantum Inf. Comput.
Aleksandrs Belovs, Ansis Rosmanis
2018 — conf
Quantum Lower Bounds for Tripartite Versions of the Hidden Shift and the Set Equality Problems.
TQC
Aleksandrs Belovs, Ansis Rosmanis
2018 J jnl
Time and space efficient quantum algorithms for detecting cycles and testing bipartiteness.
Quantum Inf. Comput.
Chris Cade, Ashley Montanaro, Aleksandrs Belovs
2017 J jnl
On a Conjecture by Christian Choffrut.
Int. J. Found. Comput. Sci.
Aleksandrs Belovs, J. Andres Montoya, Abuzer Yakaryilmaz
2017 A conf
On the Polynomial Parity Argument Complexity of the Combinatorial Nullstellensatz.
CCC
Aleksandrs Belovs, Gábor Ivanyos, Youming Qiao, Miklos Santha, Siyi Yang
2017 J jnl
On the Polynomial Parity Argument Complexity of the Combinatorial Nullstellensatz.
CoRR
Aleksandrs Belovs, Gábor Ivanyos, Youming Qiao, Miklos Santha, Siyi Yang
2017 — conf
Provably Secure Key Establishment Against Quantum Adversaries.
TQC
Aleksandrs Belovs, Gilles Brassard, Peter Høyer, Marc Kaplan, Sophie Laplante, Louis Salvail
2017 J jnl
Quantum Lower Bound for a Tripartite Version of the Hidden Shift Problem.
CoRR
Aleksandrs Belovs
2017 J jnl
Separations in Query Complexity Based on Pointer Functions.
J. ACM
Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Troy Lee, Miklos Santha, Juris Smotrovs
2016 A* conf
A polynomial lower bound for testing monotonicity.
STOC
Aleksandrs Belovs, Eric Blais
2016 J jnl
Can one quantum bit separate any pair of words with zero-error?
CoRR
Aleksandrs Belovs, Juan Andrés Montoya, Abuzer Yakaryilmaz
2016 A* conf
Efficient Quantum Algorithms for (Gapped) Group Testing and Junta Testing.
SODA
Andris Ambainis, Aleksandrs Belovs, Oded Regev, Ronald de Wolf
2016 C conf
Looking for Pairs that Hard to Separate: A Quantum Approach.
CIAA
Aleksandrs Belovs, J. Andres Montoya, Abuzer Yakaryilmaz
2016 — ch.
Quantum Algorithms for Graph Connectivity.
Encyclopedia of Algorithms
Aleksandrs Belovs
2016 A* conf
Separations in Communication Complexity Using Cheat Sheets and Information Complexity.
FOCS
Anurag Anshu, Aleksandrs Belovs, Shalev Ben-David, Mika Göös, Rahul Jain, Robin Kothari, Troy Lee, Miklos Santha
2016 J jnl
Separations in communication complexity using cheat sheets and information complexity.
CoRR
Anurag Anshu, Aleksandrs Belovs, Shalev Ben-David, Mika Göös, Rahul Jain, Robin Kothari, Troy Lee, Miklos Santha
2016 J jnl
Separations in communication complexity using cheat sheets and information complexity.
Electron. Colloquium Comput. Complex.
Anurag Anshu, Aleksandrs Belovs, Shalev Ben-David, Mika Göös, Rahul Jain, Robin Kothari, Troy Lee, Miklos Santha
2016 A* conf
Separations in query complexity based on pointer functions.
STOC
Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Troy Lee, Miklos Santha, Juris Smotrovs
2016 J jnl
Time and Space Efficient Quantum Algorithms for Detecting Cycles and Testing Bipartiteness.
CoRR
Chris Cade, Ashley Montanaro, Aleksandrs Belovs
2015 J jnl
A Polynomial Lower Bound for Testing Monotonicity.
CoRR
Aleksandrs Belovs, Eric Blais
2015 J jnl
Efficient Quantum Algorithms for (Gapped) Group Testing and Junta Testing.
CoRR
Andris Ambainis, Aleksandrs Belovs, Oded Regev, Ronald de Wolf
2015 J jnl
Quantum Algorithm for Monotonicity Testing on the Hypercube.
CoRR
Aleksandrs Belovs, Eric Blais
2015 J jnl
Quantum Algorithm for Monotonicity Testing on the Hypercube.
Theory Comput.
Aleksandrs Belovs, Eric Blais
2015 J jnl
Quantum Algorithms for Learning Symmetric Juntas via the Adversary Bound.
Comput. Complex.
Aleksandrs Belovs
2015 J jnl
Quantum lower bound for inverting a permutation with advice.
Quantum Inf. Comput.
Aran Nayebi, Scott Aaronson, Aleksandrs Belovs, Luca Trevisan
2015 J jnl
Separations in Query Complexity Based on Pointer Functions.
CoRR
Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Troy Lee, Miklos Santha, Juris Smotrovs
2015 J jnl
Separations in Query Complexity Based on Pointer Functions.
Electron. Colloquium Comput. Complex.
Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Troy Lee, Miklos Santha, Juris Smotrovs
2014 J jnl
On the Power of Non-adaptive Learning Graphs.
Comput. Complex.
Aleksandrs Belovs, Ansis Rosmanis
2014 A conf
Quantum Algorithms for Learning Symmetric Juntas via Adversary Bound.
CCC
Aleksandrs Belovs
2014 J jnl
Quantum lower bound for inverting a permutation with advice.
CoRR
Aran Nayebi, Scott Aaronson, Aleksandrs Belovs, Luca Trevisan
2014 J jnl
Quantum lower bound for inverting a permutation with advice.
Electron. Colloquium Comput. Complex.
Aran Nayebi, Scott Aaronson, Aleksandrs Belovs, Luca Trevisan
2013 A conf
Adversary lower bound for the k-sum problem.
ITCS
Aleksandrs Belovs, Robert Spalek
2013 A conf
On the Power of Non-adaptive Learning Graphs.
CCC
Aleksandrs Belovs, Ansis Rosmanis
2013 — conf
Time-Efficient Quantum Walks for 3-Distinctness.
ICALP (1)
Aleksandrs Belovs, Andrew M. Childs, Stacey Jeffery, Robin Kothari, Frédéric Magniez
2012 J jnl
Adversary Lower Bound for Element Distinctness
CoRR
Aleksandrs Belovs
2012 J jnl
Adversary Lower Bound for the k-sum Problem
CoRR
Aleksandrs Belovs, Robert Spalek
2012 A* conf
Learning-Graph-Based Quantum Algorithm for k-Distinctness.
FOCS
Aleksandrs Belovs
2012 J jnl
On the Power of Non-Adaptive Learning Graphs
CoRR
Aleksandrs Belovs
2012 A conf
Span Programs and Quantum Algorithms for st-Connectivity and Claw Detection.
ESA
Aleksandrs Belovs, Ben W. Reichardt
2012 A* conf
Span programs for functions with constant-sized 1-certificates: extended abstract.
STOC
Aleksandrs Belovs
2011 J jnl
Span-program-based quantum algorithm for the rank problem
CoRR
Aleksandrs Belovs
2008 — conf
A Criterion for Attaining the Welch Bounds with Applications for Mutually Unbiased Bases.
MMICS
Aleksandrs Belovs, Juris Smotrovs
2008 J jnl
Some Algebraic Properties of Machine Poset of Infinite Words.
RAIRO Theor. Informatics Appl.
Aleksandrs Belovs
2007 C conf
Multi-letter Reversible and Quantum Finite Automata.
Developments in Language Theory
Aleksandrs Belovs, Ansis Rosmanis, Juris Smotrovs
2006 B conf
Non-intersecting Complexity.
SOFSEM
Aleksandrs Belovs
2003 — conf
Size of Quantum Versus Deterministic Finite Automata.
VLSI
Andris Ambainis, Uldis Barbans, Agnese Belousova, Aleksandrs Belovs, Ilze Dzelme, Girts Folkmanis, Rusins Freivalds, Peteris Ledins, Rihards Opmanis, Agnis Skuskovniks