| Publication | Date of Publication | Type |
|---|
Improved algorithm and lower bound for variable time quantum search
| 2024-11-20 | Paper |
An exponential separation between quantum query complexity and the polynomial degree
| 2024-11-19 | Paper |
Application of kolmogorov complexity to inductive inference with limited memory
Lecture Notes in Computer Science | 2023-12-08 | Paper |
Quantum complexity for vector domination problem
Lecture Notes in Computer Science | 2023-08-14 | Paper |
A note about claw function with a small range
| 2023-06-26 | Paper |
Quantum bounds for 2D-grid and Dyck language
Quantum Information Processing | 2023-06-01 | Paper |
Strong dispersion property for the quantum walk on the hypercube
Journal of Physics A: Mathematical and Theoretical | 2023-02-23 | Paper |
Quantum algorithms for computational geometry problems
| 2023-02-07 | Paper |
The complexity of probabilistic versus deterministic finite automata
| 2023-01-25 | Paper |
Quantum Lower and Upper Bounds for 2D-Grid and Dyck Language
| 2022-07-18 | Paper |
All Classical Adversary Methods Are Equivalent for Total Functions
ACM Transactions on Computation Theory | 2022-03-14 | Paper |
Dataset for "Strong dispersion property for the quantum walk on the hypercube"
| 2022-01-27 | Dataset |
Automata and quantum computing
| 2021-11-12 | Paper |
Quadratic speedup for finding marked vertices by Quantum walks
Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing | 2021-01-19 | Paper |
Lower bounds and hierarchies for quantum memoryless communication protocols and quantum ordered binary decision diagrams with repeated test
SOFSEM 2018: Theory and Practice of Computer Science | 2020-10-21 | Paper |
Understanding quantum algorithms via query complexity
Proceedings of the International Congress of Mathematicians (ICM 2018) | 2020-09-22 | Paper |
All classical adversary methods are equivalent for total functions
| 2020-08-05 | Paper |
Quantum security proofs using semi-classical oracles
| 2020-03-09 | Paper |
Quantum speedups for exponential-time dynamic programming algorithms
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-10-15 | Paper |
scientific article; zbMATH DE number 7075903 (Why is no real title available?)
| 2019-07-03 | Paper |
Quadratic speedup for finding marked vertices by quantum walks
| 2019-03-18 | Paper |
Parity oblivious \(d\)-level random access codes and class of noncontextuality inequalities
Quantum Information Processing | 2019-03-15 | Paper |
On block sensitivity and fractional block sensitivity
Lobachevskii Journal of Mathematics | 2018-11-02 | Paper |
Efficient quantum algorithms for (gapped) group testing and junta testing
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms | 2018-07-16 | Paper |
Upper bound on the communication complexity of private information retrieval
Automata, Languages and Programming | 2018-07-04 | Paper |
Forrelation: a problem that optimally separates quantum from classical computing
SIAM Journal on Computing | 2018-07-04 | Paper |
Separations in query complexity based on pointer functions
Journal of the ACM | 2018-05-17 | Paper |
Upper bounds on multiparty communication complexity of shifts
STACS 96 | 2017-11-16 | Paper |
General inductive inference types based on linearly-ordered sets
STACS 96 | 2017-11-16 | Paper |
Polynomials, quantum query complexity, and Grothendieck's inequality
| 2017-10-10 | Paper |
Nearly optimal separations between communication (or query) complexity and partitions
| 2017-10-10 | Paper |
Separations in query complexity based on pointer functions
Proceedings of the forty-eighth annual ACM symposium on Theory of Computing | 2017-09-29 | Paper |
Quantum algorithm for tree size estimation, with applications to backtracking and 2-player games
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing | 2017-08-17 | Paper |
Exact quantum query complexity of \(\mathrm{EXACT}_{k,l}^n\)
SOFSEM 2017: Theory and Practice of Computer Science | 2017-04-04 | Paper |
Exact quantum query complexity of EXACT and THRESHOLD
| 2017-02-01 | Paper |
Provable Advantage for Quantum Strategies in Random Symmetric XOR Games
| 2017-02-01 | Paper |
Optimal quantum query bounds for almost all Boolean functions
| 2017-01-30 | Paper |
Quantum query complexity of almost all functions with fixed on-set size
Computational Complexity | 2016-11-30 | Paper |
Lower bounds on the deterministic and quantum communication complexity of Hamming-distance problems
ACM Transactions on Computation Theory | 2016-10-24 | Paper |
Dense quantum coding and a lower bound for 1-way quantum automata
Proceedings of the thirty-first annual ACM symposium on Theory of Computing | 2016-09-29 | Paper |
Sensitivity versus certificate complexity of Boolean functions
Computer Science – Theory and Applications | 2016-07-25 | Paper |
How rich is the structure of the intrinsic complexity of learning
Information Processing Letters | 2016-06-16 | Paper |
Superlinear advantage for exact quantum algorithms
SIAM Journal on Computing | 2016-05-12 | Paper |
Dense quantum coding and quantum finite automata
Journal of the ACM | 2015-12-07 | Paper |
Search by quantum walks on two-dimensional grid without amplitude amplification
Theory of Quantum Computation, Communication, and Cryptography | 2015-12-03 | Paper |
Size of sets with small sensitivity: a generalization of Simon's lemma
Lecture Notes in Computer Science | 2015-09-30 | Paper |
Forrelation: a problem that optimally separates quantum from classical computing
Proceedings of the forty-seventh annual ACM symposium on Theory of Computing | 2015-08-21 | Paper |
Fast matrix multiplication: limitations of the Coppersmith-Winograd method (extended abstract)
Proceedings of the forty-seventh annual ACM symposium on Theory of Computing | 2015-08-21 | Paper |
Grover's algorithm with errors
Mathematical and Engineering Methods in Computer Science | 2015-08-05 | Paper |
One-dimensional quantum walks
Proceedings of the thirty-third annual ACM symposium on Theory of computing | 2015-02-27 | Paper |
Quantum walks on graphs
Proceedings of the thirty-third annual ACM symposium on Theory of computing | 2015-02-27 | Paper |
A new protocol and lower bounds for quantum coin flipping
Proceedings of the thirty-third annual ACM symposium on Theory of computing | 2015-02-27 | Paper |
How low can approximate degree and quantum query complexity be for total Boolean functions?
Computational Complexity | 2015-01-23 | Paper |
A new quantum lower bound method, with applications to direct product theorems and time-space tradeoffs
Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing | 2014-11-25 | Paper |
Worst case analysis of non-local games
Lecture Notes in Computer Science | 2014-11-04 | Paper |
A tight lower bound on certificate complexity in terms of block sensitivity and sensitivity
Mathematical Foundations of Computer Science 2014 | 2014-10-14 | Paper |
Coins make quantum walks faster
| 2014-10-13 | Paper |
The need for structure in quantum speedups
Theory of Computing | 2014-10-06 | Paper |
Computing with highly mixed states (extended abstract)
Proceedings of the thirty-second annual ACM symposium on Theory of computing | 2014-09-26 | Paper |
Quantum lower bounds by quantum arguments
Proceedings of the thirty-second annual ACM symposium on Theory of computing | 2014-09-26 | Paper |
A quantum Lovász local lemma
Proceedings of the forty-second ACM symposium on Theory of computing | 2014-08-13 | Paper |
Recent developments in quantum algorithms and complexity
Descriptional Complexity of Formal Systems | 2014-08-07 | Paper |
Superlinear advantage for exact quantum algorithms
Proceedings of the forty-eighth annual ACM symposium on Theory of Computing | 2014-08-07 | Paper |
Weak parity
Automata, Languages, and Programming | 2014-07-01 | Paper |
Tighter relations between sensitivity and other complexity measures
Automata, Languages, and Programming | 2014-07-01 | Paper |
A quantum Lovász local lemma
Journal of the ACM | 2014-02-17 | Paper |
On symmetric nonlocal games
Theoretical Computer Science | 2014-01-10 | Paper |
Quantum strategies are better than classical in almost any XOR game
Automata, Languages, and Programming | 2013-08-12 | Paper |
Quantum search with variable times
| 2013-03-19 | Paper |
Variable time amplitude amplification and quantum algorithms for linear algebra problems
| 2012-08-23 | Paper |
Superiority of exact quantum automata for promise problems
Information Processing Letters | 2012-05-04 | Paper |
Random tensor theory: Extending random matrix theory to mixtures of random product states
Communications in Mathematical Physics | 2012-03-01 | Paper |
The quantum query complexity of certification
| 2011-10-05 | Paper |
Limits on entropic uncertainty relations for 3 and more MUBs
| 2011-10-05 | Paper |
Quantum property testing for bounded-degree graphs
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2011-08-17 | Paper |
Quantum search of spatial regions
Theory of Computing | 2011-05-24 | Paper |
A new quantum lower bound method, with an application to a strong direct product theorem for quantum search
Theory of Computing | 2011-05-24 | Paper |
scientific article; zbMATH DE number 5899233 (Why is no real title available?)
Theory of Computing | 2011-05-24 | Paper |
Any AND-OR formula of size \(N\) can be evaluated in time \(N^{1/2+o(1)}\) on a quantum computer
SIAM Journal on Computing | 2011-01-17 | Paper |
Quantum search with variable times
Theory of Computing Systems | 2010-10-06 | Paper |
scientific article; zbMATH DE number 5788514 (Why is no real title available?)
| 2010-09-20 | Paper |
New developments in quantum algorithms
Mathematical Foundations of Computer Science 2010 | 2010-09-03 | Paper |
Quantum algorithms a decade after Shor
Proceedings of the thirty-sixth annual ACM symposium on Theory of computing | 2010-08-15 | Paper |
Nonlocal Quantum XOR Games for Large Number of Players
Lecture Notes in Computer Science | 2010-06-17 | Paper |
Transformations that preserve learnability
Lecture Notes in Computer Science | 2010-04-27 | Paper |
Nonmalleable encryption of quantum information
Journal of Mathematical Physics | 2009-12-14 | Paper |
A new quantum lower bound method, with applications to direct product theorems and time-space tradeoffs
Algorithmica | 2009-08-31 | Paper |
Improved constructions of quantum automata
Theoretical Computer Science | 2009-05-19 | Paper |
Public Key Cryptography – PKC 2004
Lecture Notes in Computer Science | 2009-05-14 | Paper |
Quantum Query Complexity of Boolean Functions with Small On-Sets
Algorithms and Computation | 2009-01-29 | Paper |
Improved Constructions of Quantum Automata
Theory of Quantum Computation, Communication, and Cryptography | 2009-01-13 | Paper |
The minimum distance problem for two-way entanglement purification
IEEE Transactions on Information Theory | 2008-12-21 | Paper |
Computing with highly mixed states
Journal of the ACM | 2008-12-21 | Paper |
ROM-based computation: quantum versus classical
| 2008-09-03 | Paper |
Probabilistic and team PFIN-type learning: General properties
Journal of Computer and System Sciences | 2008-06-10 | Paper |
Lower Bounds on the Deterministic and Quantum Communication Complexities of Hamming-Distance Problems
Algorithms and Computation | 2008-04-24 | Paper |
Quantum Walk Algorithm for Element Distinctness
SIAM Journal on Computing | 2008-03-28 | Paper |
Quantum Algorithms for Matching and Network Flows
STACS 2006 | 2008-03-19 | Paper |
Quantum Walks with Multiple or Moving Marked Locations
SOFSEM 2008: Theory and Practice of Computer Science | 2008-03-07 | Paper |
Quantum Random Walks – New Method for Designing Quantum Algorithms
SOFSEM 2008: Theory and Practice of Computer Science | 2008-03-07 | Paper |
STACS 2004
Lecture Notes in Computer Science | 2007-10-01 | Paper |
STACS 2004
Lecture Notes in Computer Science | 2007-10-01 | Paper |
Improved Algorithms for Quantum Identification of Boolean Oracles
Algorithm Theory – SWAT 2006 | 2007-09-07 | Paper |
Improved algorithms for quantum identification of Boolean oracles
Theoretical Computer Science | 2007-06-06 | Paper |
Quantum identification of Boolean oracles
| 2007-05-09 | Paper |
Algebraic results on quantum automata
Theory of Computing Systems | 2006-10-25 | Paper |
Polynomial degree vs. quantum query complexity
Journal of Computer and System Sciences | 2006-04-28 | Paper |
Parsimony hierarchies for inductive inference
Journal of Symbolic Logic | 2005-08-29 | Paper |
A new protocol and lower bounds for quantum coin flipping
Journal of Computer and System Sciences | 2004-11-22 | Paper |
QUANTUM WALKS AND THEIR ALGORITHMIC APPLICATIONS
International Journal of Quantum Information | 2004-09-24 | Paper |
scientific article; zbMATH DE number 2077145 (Why is no real title available?)
| 2004-07-01 | Paper |
scientific article; zbMATH DE number 2062211 (Why is no real title available?)
| 2004-03-25 | Paper |
The Quantum Communication Complexity of Sampling
SIAM Journal on Computing | 2004-01-08 | Paper |
Exact results for accepting probabilities of quantum automata.
Theoretical Computer Science | 2003-08-17 | Paper |
Two-way finite automata with quantum and classical states.
Theoretical Computer Science | 2003-01-21 | Paper |
scientific article; zbMATH DE number 1834645 (Why is no real title available?)
| 2002-11-25 | Paper |
Quantum lower bounds by quantum arguments
Journal of Computer and System Sciences | 2002-09-12 | Paper |
A note on quantum black-box complexity of almost all Boolean functions
Information Processing Letters | 2002-07-25 | Paper |
On learning formulas in the limit and with assurance.
Information Processing Letters | 2002-07-25 | Paper |
Delayed binary search, or playing twenty questions with a procrastinator
Algorithmica | 2002-05-21 | Paper |
The communication complexity of enumeration, elimination, and selection
Journal of Computer and System Sciences | 2002-04-11 | Paper |
Average-case quantum query complexity
Journal of Physics A: Mathematical and General | 2002-01-27 | Paper |
scientific article; zbMATH DE number 1688355 (Why is no real title available?)
| 2002-01-09 | Paper |
Probabilistic inductive inference: A survey
Theoretical Computer Science | 2001-08-20 | Paper |
Hierarchies of probabilistic and team FIN-learning
Theoretical Computer Science | 2001-08-20 | Paper |
scientific article; zbMATH DE number 1512689 (Why is no real title available?)
| 2001-07-29 | Paper |
scientific article; zbMATH DE number 1405684 (Why is no real title available?)
| 2000-09-26 | Paper |
scientific article; zbMATH DE number 1507556 (Why is no real title available?)
| 2000-09-14 | Paper |
scientific article; zbMATH DE number 1500513 (Why is no real title available?)
| 2000-09-04 | Paper |
Ordinal mind change complexity of language identification
Theoretical Computer Science | 2000-08-23 | Paper |
scientific article; zbMATH DE number 1490003 (Why is no real title available?)
| 2000-08-13 | Paper |
scientific article; zbMATH DE number 1416102 (Why is no real title available?)
| 2000-05-11 | Paper |
scientific article; zbMATH DE number 1405642 (Why is no real title available?)
| 2000-04-25 | Paper |
scientific article; zbMATH DE number 1283992 (Why is no real title available?)
| 1999-10-14 | Paper |
scientific article; zbMATH DE number 1222576 (Why is no real title available?)
| 1999-03-02 | Paper |
scientific article; zbMATH DE number 1305481 (Why is no real title available?)
| 1999-01-01 | Paper |
scientific article; zbMATH DE number 1104340 (Why is no real title available?)
| 1998-05-29 | Paper |
scientific article; zbMATH DE number 1104353 (Why is no real title available?)
| 1998-02-02 | Paper |
Communication complexity in a 3-computer model
Algorithmica | 1996-10-16 | Paper |
scientific article; zbMATH DE number 1960352 (Why is no real title available?)
| 1996-01-01 | Paper |
scientific article; zbMATH DE number 1960351 (Why is no real title available?)
| 1996-01-01 | Paper |
