Miklos Santha
CQT Distinguished Fellow
Centre for Quantum Technologies , National University of Singapore
Emeritus Research Director
French National Centre for Scientific Research (CNRS)
S15-04-02
Miklos Santha received his PhD degree in Mathematics from the Université Paris Diderot in 1983 and the Doctorat d’Etat in Computer Science from the Université Paris-Sud, Orsay in 1988. In 1988, he joined the Centre National de la Recherche Scientifique where he is Senior Researcher in Computer Science in the Research Institute on the Foundations of Computer Science (IRIF) in Paris. Since 2008 he is also Visiting Research Professor and Principal Investigator in the Centre for Quantum Technologies at the National University of Singapore. His research interests include quantum computing, randomness and complexity theory. He was a Humboldt Fellow in the Max Planck Institute in Saarbrücken from 1990 to 1991. In the last three decades he was the coordinator for the CNRS of several EU projects on randomised and quantum algorithms.
Preprints & Publications
Quantum algorithm for stochastic optimal stopping problems with applications in finance
Classical and quantum dynamic programming for Subset-Sum and variants
Total Functions in QMA
Quantum algorithms for hedging and the learning of Ising models
Quantum algorithms for graph problems with cut queries
On the cut dimension of a graph
Characterizing the intersection of QMA and coQMA
Strategies for quantum races
Quantum and Classical Algorithms for Approximate Submodular Function Minimization
Linear time algorithm for quantum 2SAT
Polynomial Interpolation and Identity Testing from High Powers over Finite Fields
A new public-key cryptosystem via Mersenne numbers
On the Complexity of Trial and Error for Constraint Satisfaction Problems
On solving systems of diagonal polynomial equations over finite fields
A Composition Theorem for Randomized Query Complexity
On the Polynomial Parity Argument complexity of the Combinatorial Nullstellensatz
Quadratically Tight Relations for Randomized Query Complexity
Separations in Query Complexity Based on Pointer Functions
Separation in query complexity based on pointer functions
On the complexity of probabilistic trials for hidden satisfiability problems
Separations in communication complexity using cheat sheets and information complexity
Improved bounds for the randomized decision tree complexity of recursive majority
Improved quantum query algorithms for Triangle Finding and Associativity Testing
Nonlocality and conflicting interest games
Quantum and randomized query complexities
Separating decision tree complexity from subcube partition complexity
Generalized Wong sequences and their applications to Edmonds
On the complexity of trial and error for constraint satisfaction problems
An efficient quantum algorithm for finding hidden parabolic subgroups in the general linear group
Polynomial time quantum algorithms for certain bivariate hidden polynomial problems
Hidden Translation and Translating Coset in Quantum Computing
Hidden Symmetry Subgroup Problems
Query complexity of matroids
An efficient quantum algorithm for the hidden subgroup problem in nil-2 groups
On the hitting times of quantum versus random walks
On the power of a unique quantum witness
Learning graph based quantum query algorithms for finding constant-size subgraphs
New bounds on the classical and quantum communication complexity of some graph properties
Search via Quantum Walk
The complexity of approximate Nash equilibrium in congestion games with negative delays
Optimal Direct Sum Results for Deterministic and Randomized Decision Tree Complexity
Quantum testers for hidden group properties
On the black-box complexity of Sperner’s Lemma
Quantum and classical query complexities of local search are polynomially related
Approximate Nash equilibria for multi-player games
Quantum walk based search algorithms
An efficient quantum algorithm for the hidden subgroup problem in nil-2 groups
Quantum algorithms for the triangle problem
Self-testing of universal and fault-tolerant sets of quantum gates
On learning linear functions from subset and its applications in quantum computing
Quantum generalizations of the polynomial hierarchy with applications to QMA(2)
Quantum algorithms for hedging and the Sparsitron
Discrete logarithm and Diffie-Hellman problems in identity black-box groups