Miklos Santha

According to our database1, Miklos Santha authored at least 80 papers between 1984 and 2020.

Collaborative distances:
  • Dijkstra number2 of four.
  • Erdős number3 of two.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

On csauthors.net:

Bibliography

2020
Quadratically Tight Relations for Randomized Query Complexity.
Theory Comput. Syst., 2020

2019
Quantum and classical algorithms for approximate submodular function minimization.
Quantum Information & Computation, 2019

Discrete logarithm and Diffie-Hellman problems in identity black-box groups.
CoRR, 2019

Strategies for Quantum Races.
Proceedings of the 10th Innovations in Theoretical Computer Science Conference, 2019

A Composition Theorem for Randomized Query Complexity via Max-Conflict Complexity.
Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

2018
Linear-Time Algorithm for Quantum 2SAT.
Theory of Computing, 2018

On the complexity of trial and error for constraint satisfaction problems.
J. Comput. Syst. Sci., 2018

On the randomised query complexity of composition.
CoRR, 2018

Polynomial Interpolation and Identity Testing from High Powers Over Finite Fields.
Algorithmica, 2018

Quantum Generalizations of the Polynomial Hierarchy with Applications to QMA(2).
Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science, 2018

On Learning Linear Functions from Subset and Its Applications in Quantum Computing.
Proceedings of the 26th Annual European Symposium on Algorithms, 2018

2017
Solving systems of diagonal polynomial equations over finite fields.
Theor. Comput. Sci., 2017

Separations in Query Complexity Based on Pointer Functions.
J. ACM, 2017

A New Public-Key Cryptosystem via Mersenne Numbers.
IACR Cryptology ePrint Archive, 2017

Quadratically Tight Relations for Randomized Query Complexity.
Electronic Colloquium on Computational Complexity (ECCC), 2017

A Composition Theorem for Randomized Query complexity.
Electronic Colloquium on Computational Complexity (ECCC), 2017

Improved Quantum Query Algorithms for Triangle Detection and Associativity Testing.
Algorithmica, 2017

On the Polynomial Parity Argument Complexity of the Combinatorial Nullstellensatz.
Proceedings of the 32nd Computational Complexity Conference, 2017

2016
Improved bounds for the randomized decision tree Complexity of recursive majority.
Random Struct. Algorithms, 2016

Separations in communication complexity using cheat sheets and information complexity.
Electronic Colloquium on Computational Complexity (ECCC), 2016

On the Complexity of Probabilistic Trials for Hidden Satisfiability Problems.
Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science, 2016

2015
Generalized Wong sequences and their applications to Edmonds' problems.
J. Comput. Syst. Sci., 2015

Quantum and Randomized Query Complexities (Extended Abstract).
Proceedings of the Theory and Applications of Models of Computation, 2015

Separating Decision Tree Complexity from Subcube Partition Complexity.
Proceedings of the Approximation, 2015

2014
Hidden Translation and Translating Coset in Quantum Computing.
SIAM J. Comput., 2014

Polynomial time quantum algorithms for certain bivariate hidden polynomial problems.
Quantum Information & Computation, 2014

An Efficient Quantum Algorithm for Finding Hidden Parabolic Subgroups in the General Linear Group.
Proceedings of the Mathematical Foundations of Computer Science 2014, 2014

2013
Hidden Symmetry Subgroup Problems.
SIAM J. Comput., 2013

Improved quantum query algorithms for triangle finding and associativity testing.
Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

2012
On the Power of a Unique Quantum Witness.
Theory of Computing, 2012

Query complexity of matroids.
Electronic Colloquium on Computational Complexity (ECCC), 2012

Learning graph based quantum query algorithms for finding constant-size subgraphs.
Chicago J. Theor. Comput. Sci., 2012

On the Hitting Times of Quantum Versus Random Walks.
Algorithmica, 2012

An Efficient Quantum Algorithm for the Hidden Subgroup Problem in Nil-2 Groups.
Algorithmica, 2012

New bounds on the classical and quantum communication complexity of some graph properties.
Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2012

2011
Search via Quantum Walk.
SIAM J. Comput., 2011

A learning graph based quantum query algorithm for finding constant-size subgraphs
CoRR, 2011

The Complexity of Approximate Nash Equilibrium in Congestion Games with Negative Delays.
Proceedings of the Internet and Network Economics - 7th International Workshop, 2011

2010
Optimal direct sum results for deterministic and randomized decision tree complexity.
Inf. Process. Lett., 2010

Improved bounds for the randomized decision tree complexity of recursive majority.
Electronic Colloquium on Computational Complexity (ECCC), 2010

Quantization of Random Walks: Search Algorithms and Hitting Time.
Proceedings of the Computer Science, 2010

2009
On the Black-Box Complexity of Sperner's Lemma.
Theory Comput. Syst., 2009

Quantum Testers for Hidden Group Properties.
Fundam. Inform., 2009

Quantum and Classical Query Complexities of Local Search Are Polynomially Related.
Algorithmica, 2009

2008
Quantum Walk Based Search Algorithms.
Proceedings of the Theory and Applications of Models of Computation, 2008

Approximate Nash Equilibria for Multi-player Games.
Proceedings of the Algorithmic Game Theory, First International Symposium, 2008

2007
Quantum Algorithms for the Triangle Problem.
SIAM J. Comput., 2007

Self-Testing of Universal and Fault-Tolerant Sets of Quantum Gates.
SIAM J. Comput., 2007

An Efficient Quantum Algorithm for the Hidden Subgroup Problem in Extraspecial Groups.
Proceedings of the STACS 2007, 2007

2006
Locally 2-Dimensional Sperner Problems Complete for the Polynomial Parity Argument Classes.
Proceedings of the Algorithms and Complexity, 6th Italian Conference, 2006

2005
Quantum Algorithms for Element Distinctness.
SIAM J. Comput., 2005

Efficient testing of groups.
Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005

2003
Semantical Counting Circuits.
Theory Comput. Syst., 2003

Approximate testing with error relative to input size.
J. Comput. Syst. Sci., 2003

Efficient Quantum Algorithms For Some Instances Of The Non-Abelian Hidden Subgroup Problem.
Int. J. Found. Comput. Sci., 2003

Hidden translation and orbit coset in quantum computing.
Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

2002
A Decision Procedure for Unitary Linear Quantum Cellular Automata.
SIAM J. Comput., 2002

Efficient Approximation Algorithms for the SUBSET-SUMS EQUALITY Problem.
J. Comput. Syst. Sci., 2002

2001
Exact and Approximate Testing/Correcting of Algebraic Functions: A Survey
Electronic Colloquium on Computational Complexity (ECCC), 2001

1999
On the Approximation of Finding A(nother) Hamiltonian Cycle in Cubic Hamiltonian Graphs.
J. Algorithms, 1999

Approximate Testing with Relative Error.
Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

1998
Verifying the Determinant in Parallel.
Computational Complexity, 1998

Average-Case Analysis of the Merging Algorithm of Hwang and Lin.
Algorithmica, 1998

On the Approximation of Finding A(nother) Hamilton Cycle in Cubic Hamilton Graphs (Extended Abstract).
Proceedings of the STACS 98, 1998

1997
A decision procedure for well-formed linear quantum cellular automata.
Random Struct. Algorithms, 1997

1996
Oblivious transfers and intersecting codes.
IEEE Trans. Information Theory, 1996

1995
On the Monte Carlo Boolean Decision Tree Complexity of Read-Once Formulae.
Random Struct. Algorithms, 1995

A Parallel Reduction of Hamiltonian Cycle to Hamiltonian Path in Tournaments.
J. Algorithms, 1995

1994
On the Interactive Complexity of Graph Reliability.
Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1994

1993
Two Probabilistic Results on Merging.
SIAM J. Comput., 1993

Limiting Negations in Constant Depth Circuits.
SIAM J. Comput., 1993

Parallel searching of multidimensional cubes.
Discret. Math., 1993

1992
Deciding Bisimilarity is P-Complete.
Formal Asp. Comput., 1992

1991
Polynomial Size Constant Depth Circuits with a Limited Number of Negations.
Proceedings of the STACS 91, 1991

Parallel Complexity in the Design and Analysis on Conurrent Systems.
Proceedings of the PARLE '91: Parallel Architectures and Languages Europe, 1991

On the Reversibility of Oblivious Transfer.
Proceedings of the Advances in Cryptology, 1991

1989
Relativized Arthur-Merlin versus Merlin-Arthur Games
Inf. Comput., January, 1989

1987
On Using Deterministic Functions to Reduce Randomness in Probabilistic Algorithms
Inf. Comput., September, 1987

1986
Generating Quasi-random Sequences from Semi-random Sources.
J. Comput. Syst. Sci., 1986

1984
Generating Quasi-Random Sequences from Slightly-Random Sources (Extended Abstract)
Proceedings of the 25th Annual Symposium on Foundations of Computer Science, 1984


  Loading...