31 citations · 199 across the 33 of their papers we have counts for
7 papers · 1 filter
Quantum Communication Complexity of Distribution Testing
Aleksandrs Belovs, Arturo Castellanos, François Le Gall +2
The classical communication complexity of testing closeness of discrete distributions has recently been studied by Andoni, Malkin and Nosatzki (ICALP'19). In this problem, two play…
Testing convexity of functions over finite domains
Aleksandrs Belovs, Eric Blais, Abhinav Bommireddi
We establish new upper and lower bounds on the number of queries required to test convexity of functions over various discrete domains. 1. We provide a simplified version of the no…
Adaptive Lower Bound for Testing Monotonicity on the Line
Aleksandrs Belovs
In the property testing model, the task is to distinguish objects possessing some property from the objects that are far from it. One of such properties is monotonicity, when the o…
On the Polynomial Parity Argument Complexity of the Combinatorial Nullstellensatz
Aleksandrs Belovs, Gábor Ivanyos, Youming Qiao +2
The complexity class PPA consists of NP-search problems which are reducible to the parity principle in undirected graphs. It contains a wide variety of interesting problems from gr…
A Polynomial Lower Bound for Testing Monotonicity
Aleksandrs Belovs, Eric Blais
We show that every algorithm for testing -variate Boolean functions for monotonicity must have query complexity . All previous lower bounds for this problem we…
Efficient Quantum Algorithms for (Gapped) Group Testing and Junta Testing
Andris Ambainis, Aleksandrs Belovs, Oded Regev +1
In the -junta testing problem, a tester has to efficiently decide whether a given function is a -junta (i.e., depends on at most of its i…