194 citations · 1.9k across the 115 of their papers we have counts for
22 papers · 1 filter
A Hierarchy for Constant Communication Complexity
Andris Ambainis, Hartmut Klauck, Debbie Lim
Similarly to the Chomsky hierarchy, we offer a classification of communication complexity measures such that these measures are organized into equivalence classes. Different from p…
Matching Triangles and Triangle Collection: Hardness based on a Weak Quantum Conjecture
Andris Ambainis, Harry Buhrman, Koen Leijnse +2
Classically, for many computational problems one can conclude time lower bounds conditioned on the hardness of one or more of key problems: k-SAT, 3SUM and APSP. More recently, sim…
On Block Sensitivity and Fractional Block Sensitivity
Andris Ambainis, Krišjānis Prūsis, Jevgēnijs Vihrovs
We investigate the relation between the block sensitivity and fractional block sensitivity complexity measures of Boolean functions. While it is know…
All Classical Adversary Methods are Equivalent for Total Functions
Andris Ambainis, Martins Kokainis, Krišjānis Prūsis +2
We show that all known classical adversary lower bounds on randomized query complexity are equivalent for total functions, and are equal to the fractional block sensitivity $\text{…
Lower Bounds and Hierarchies for Quantum Memoryless Communication Protocols and Quantum Ordered Binary Decision Diagrams with Repeated Test
Farid Ablayev, Andris Ambainis, Kamil Khadiev +1
We explore multi-round quantum memoryless communication protocols. These are restricted version of multi-round quantum communication protocols. The "memoryless" term means that pla…
Nearly optimal separations between communication (or query) complexity and partitions
Robin Kothari
We show a nearly quadratic separation between deterministic communication complexity and the logarithm of the partition number, which is essentially optimal. This improves upon a r…
Almost quadratic gap between partition complexity and query/communication complexity
Andris Ambainis, Martins Kokainis
We show nearly quadratic separations between two pairs of complexity measures: 1. We show that there is a Boolean function with where is t…
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…
Separations in Query Complexity Based on Pointer Functions
Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs +3
In 1986, Saks and Wigderson conjectured that the largest separation between deterministic and zero-error randomized query complexity for a total boolean function is given by the fu…
Sensitivity versus Certificate Complexity of Boolean Functions
Andris Ambainis, Krišjānis Prūsis, Jevgēnijs Vihrovs
Sensitivity, block sensitivity and certificate complexity are basic complexity measures of Boolean functions. The famous sensitivity conjecture claims that sensitivity is polynomia…
Fast Matrix Multiplication: Limitations of the Laser Method
Andris Ambainis, Yuval Filmus, François Le Gall
Until a few years ago, the fastest known matrix multiplication algorithm, due to Coppersmith and Winograd (1990), ran in time . Recently, a surge of activity by Stot…
Tighter Relations Between Sensitivity and Other Complexity Measures
Andris Ambainis, Mohammad Bavarian, Yihan Gao +3
Sensitivity conjecture is a longstanding and fundamental open problem in the area of complexity measures of Boolean functions and decision tree complexity. The conjecture postulate…
Size of Sets with Small Sensitivity: a Generalization of Simon's Lemma
Andris Ambainis, Jevgēnijs Vihrovs
We study the structure of sets with small sensitivity. The well-known Simon's lemma says that any of sensitivity must be of size a…
Exact quantum algorithms have advantage for almost all Boolean functions
Andris Ambainis, Jozef Gruska, Shenggen Zheng
It has been proved that almost all -bit Boolean functions have exact classical query complexity . However, the situation seemed to be very different when we deal with exact q…
A Tight Lower Bound on Certificate Complexity in Terms of Block Sensitivity and Sensitivity
Andris Ambainis, Krišjānis Prūsis
Sensitivity, certificate complexity and block sensitivity are widely used Boolean function complexity measures. A longstanding open problem, proposed by Nisan and Szegedy, is wheth…
Weak Parity
Scott Aaronson, Andris Ambainis, Kaspars Balodis +1
We study the query complexity of Weak Parity: the problem of computing the parity of an n-bit input string, where one only has to succeed on a 1/2+eps fraction of input strings, bu…
New upper bound on block sensitivity and certificate complexity in terms of sensitivity
Andris Ambainis, Yihan Gao, Jieming Mao +2
Sensitivity \cite{CD82,CDR86} and block sensitivity \cite{Nisan91} are two important complexity measures of Boolean functions. A longstanding open problem in decision tree complexi…
New separation between and
Andris Ambainis, Xiaoming Sun
In this note we give a new separation between sensitivity and block sensitivity of Boolean functions: .
Superiority of exact quantum automata for promise problems
Andris Ambainis, Abuzer Yakaryilmaz
In this note, we present an infinite family of promise problems which can be solved exactly by just tuning transition amplitudes of a two-state quantum finite automata operating in…
Lower bounds on the Deterministic and Quantum Communication Complexity of Hamming Distance
Andris Ambainis, William Gasarch, Aravind Srinavasan +1
Alice and Bob want to know if two strings of length n are almost equal. That is, do they differ on \textit{at most} a bits? Let 0\leq a\leq n-1. We show that any deterministic prot…
Cryptographic Randomized Response Techniques
Andris Ambainis, Markus Jakobsson, Helger Lipmaa
We develop cryptographically secure techniques to guarantee unconditional privacy for respondents to polls. Our constructions are efficient and practical, and are shown not to allo…
Two-way finite automata with quantum and classical states
Andris Ambainis, John Watrous
We introduce 2-way finite automata with quantum and classical states (2qcfa's). This is a variant on the 2-way quantum finite automata (2qfa) model which may be simpler to implemen…