Miklos Santha

According to our database, Miklos Santha authored at least 98 papers between 1984 and 2025.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of two.

2025

Reconquering Bell sampling on qudits: stabilizer learning and testing, quantum pseudorandomness bounds, and more.

Jonathan Allcock, João F. Doriguello, Gábor Ivanyos, Miklos Santha

CoRR, October, 2025

The Local Hamiltonian Problem for Quasi-Quantum States: A Toy Model for the Quantum PCP Conjecture (Extended Abstract).

Itai Arad, Miklos Santha

Proceedings of the 16th Innovations in Theoretical Computer Science Conference, 2025

On the Quantum Time Complexity of Divide and Conquer.

Jonathan Allcock, Jinge Bao, Aleksandrs Belovs, Troy Lee, Miklos Santha

Proceedings of the 52nd International Colloquium on Automata, Languages, and Programming, 2025

2024

Constant-depth circuits for Boolean functions and quantum memory devices using multi-qubit gates.

Jonathan Allcock, Jinge Bao, João F. Doriguello, Alessandro Luongo, Miklos Santha

Quantum, 2024

Quasi-quantum states and the quasi-quantum PCP theorem.

Itai Arad, Miklos Santha

CoRR, 2024

Polynomial Time Algorithms for Integer Programming and Unbounded Subset Sum in the Total Regime.

Divesh Aggarwal, Antoine Joux, Miklos Santha, Karol Wegrzycki

CoRR, 2024

Beyond Bell sampling: stabilizer state learning and quantum pseudorandomness lower bounds on qudits.

Jonathan Allcock, João F. Doriguello, Gábor Ivanyos, Miklos Santha

CoRR, 2024

2023

Quantum Alphatron: quantum advantage for learning with kernels and noise.

Siyi Yang, Naixu Guo, Miklos Santha, Patrick Rebentrost

Quantum, November, 2023

Optimal Composition Theorem for Randomized Query Complexity.

Dmytro Gavinsky, Troy Lee, Miklos Santha, Swagato Sanyal

Theory Comput., 2023

Constant-depth circuits for Uniformly Controlled Gates and Boolean functions with application to quantum memory circuits.

Jonathan Allcock, Jinge Bao, João F. Doriguello, Alessandro Luongo, Miklos Santha

CoRR, 2023

2022

Quantum Algorithm for Stochastic Optimal Stopping Problems with Applications in Finance.

João F. Doriguello, Alessandro Luongo, Jinge Bao, Patrick Rebentrost, Miklos Santha

Proceedings of the 17th Conference on the Theory of Quantum Computation, 2022

Classical and Quantum Algorithms for Variants of Subset-Sum via Dynamic Programming.

Jonathan Allcock, Yassine Hamoudi, Antoine Joux, Felix Klingelhöfer, Miklos Santha

Proceedings of the 30th Annual European Symposium on Algorithms, 2022

2021

Characterising the intersection of QMA and coQMA.

Serge Massar, Miklos Santha

Quantum Inf. Process., 2021

Total functions in QMA.

Serge Massar, Miklos Santha

Quantum Inf. Process., 2021

Classical and quantum dynamic programming for Subset-Sum and variants.

Jonathan Allcock, Yassine Hamoudi, Antoine Joux, Felix Klingelhöfer, Miklos Santha

CoRR, 2021

Quantum algorithms for graph problems with cut queries.

Troy Lee, Miklos Santha, Shengyu Zhang

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

On the Cut Dimension of a Graph.

Troy Lee, Tongyang Li, Miklos Santha, Shengyu Zhang

Proceedings of the 36th Computational Complexity Conference, 2021

2019

Quantum and classical algorithms for approximate submodular function minimization.

Yassine Hamoudi, Patrick Rebentrost, Ansis Rosmanis, Miklos Santha

Quantum Inf. Comput., 2019

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

Gábor Ivanyos, Antoine Joux, Miklos Santha

CoRR, 2019

Strategies for Quantum Races.

Troy Lee, Maharshi Ray, Miklos Santha

Proceedings of the 10th Innovations in Theoretical Computer Science Conference, 2019

A Composition Theorem for Randomized Query Complexity via Max-Conflict Complexity.

Dmitry Gavinsky, Troy Lee, Miklos Santha, Swagato Sanyal

Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

2018

Quantum Attacks on Bitcoin, and How to Protect Against Them.

Divesh Aggarwal, Gavin K. Brennen, Troy Lee, Miklos Santha, Marco Tomamichel

Ledger, 2018

On the randomised query complexity of composition.

Dmitry Gavinsky, Troy Lee, Miklos Santha

CoRR, 2018

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

Gábor Ivanyos, Marek Karpinski, Miklos Santha, Nitin Saxena, Igor E. Shparlinski

Algorithmica, 2018

Quantum Generalizations of the Polynomial Hierarchy with Applications to QMA(2).

Sevag Gharibian, Miklos Santha, Jamie Sikora, Aarthi Sundaram, Justin Yirka

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.

Gábor Ivanyos, Anupam Prakash, Miklos Santha

Proceedings of the 26th Annual European Symposium on Algorithms, 2018

Quadratically Tight Relations for Randomized Query Complexity.

Rahul Jain, Hartmut Klauck, Srijita Kundu, Troy Lee, Miklos Santha, Swagato Sanyal, Jevgenijs Vihrovs

Proceedings of the Computer Science - Theory and Applications, 2018

A New Public-Key Cryptosystem via Mersenne Numbers.

Divesh Aggarwal, Antoine Joux, Anupam Prakash, Miklos Santha

Proceedings of the Advances in Cryptology - CRYPTO 2018, 2018

2017

Quadratically Tight Relations for Randomized Query Complexity.

Dmitry Gavinsky, Rahul Jain, Hartmut Klauck, Srijita Kundu, Troy Lee, Miklos Santha, Swagato Sanyal, Jevgenijs Vihrovs

Electron. Colloquium Comput. Complex., 2017

Improved Quantum Query Algorithms for Triangle Detection and Associativity Testing.

Troy Lee, Frédéric Magniez, Miklos Santha

Algorithmica, 2017

A Composition Theorem for Randomized Query Complexity.

Anurag Anshu, Dmitry Gavinsky, Rahul Jain, Srijita Kundu, Troy Lee, Priyanka Mukhopadhyay, Miklos Santha, Swagato Sanyal

Proceedings of the 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2017

On the Polynomial Parity Argument Complexity of the Combinatorial Nullstellensatz.

Aleksandrs Belovs, Gábor Ivanyos, Youming Qiao, Miklos Santha, Siyi Yang

Proceedings of the 32nd Computational Complexity Conference, 2017

2016

Improved bounds for the randomized decision tree Complexity of recursive majority.

Frédéric Magniez, Ashwin Nayak, Miklos Santha, Jonah Sherman, Gábor Tardos, David Xiao

Random Struct. Algorithms, 2016

Separations in query complexity based on pointer functions.

Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Troy Lee, Miklos Santha, Juris Smotrovs

Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

On the Complexity of Probabilistic Trials for Hidden Satisfiability Problems.

Itai Arad, Adam Bouland, Daniel Grier, Miklos Santha, Aarthi Sundaram, Shengyu Zhang

Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science, 2016

Linear Time Algorithm for Quantum 2SAT.

Itai Arad, Miklos Santha, Aarthi Sundaram, Shengyu Zhang

Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

Separations in Communication Complexity Using Cheat Sheets and Information Complexity.

Anurag Anshu, Aleksandrs Belovs, Shalev Ben-David, Mika Göös, Rahul Jain, Robin Kothari, Troy Lee, Miklos Santha

Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, 2016

2015

Quantum and Randomized Query Complexities (Extended Abstract).

Miklos Santha

Proceedings of the Theory and Applications of Models of Computation, 2015

On Solving Systems of Diagonal Polynomial Equations Over Finite Fields.

Gábor Ivanyos, Miklos Santha

Proceedings of the Frontiers in Algorithmics - 9th International Workshop, 2015

Separating Decision Tree Complexity from Subcube Partition Complexity.

Robin Kothari, David Racicot-Desloges, Miklos Santha

Proceedings of the Approximation, 2015

2014

Hidden Translation and Translating Coset in Quantum Computing.

Katalin Friedl, Gábor Ivanyos, Frédéric Magniez, Miklos Santha, Pranab Sen

SIAM J. Comput., 2014

Polynomial time quantum algorithms for certain bivariate hidden polynomial problems.

Thomas Decker, Peter Høyer, Gábor Ivanyos, Miklos Santha

Quantum Inf. Comput., 2014

Generalized Wong sequences and their applications to Edmonds' problems.

Gábor Ivanyos, Marek Karpinski, Youming Qiao, Miklos Santha

Proceedings of the 31st International Symposium on Theoretical Aspects of Computer Science, 2014

An Efficient Quantum Algorithm for Finding Hidden Parabolic Subgroups in the General Linear Group.

Thomas Decker, Gábor Ivanyos, Raghav Kulkarni, Youming Qiao, Miklos Santha

Proceedings of the Mathematical Foundations of Computer Science 2014, 2014

On the Complexity of Trial and Error for Constraint Satisfaction Problems.

Gábor Ivanyos, Raghav Kulkarni, Youming Qiao, Miklos Santha, Aarthi Sundaram

Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

2013

Hidden Symmetry Subgroup Problems.

Thomas Decker, Gábor Ivanyos, Miklos Santha, Pawel Wocjan

SIAM J. Comput., 2013

Improved quantum query algorithms for triangle finding and associativity testing.

Troy Lee, Frédéric Magniez, Miklos Santha

Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

Query Complexity of Matroids.

Raghav Kulkarni, Miklos Santha

Proceedings of the Algorithms and Complexity, 8th International Conference, 2013

2012

Learning graph based quantum query algorithms for finding constant-size subgraphs.

Troy Lee, Frédéric Magniez, Miklos Santha

Chic. J. Theor. Comput. Sci., 2012

New bounds on the classical and quantum communication complexity of some graph properties.

Gábor Ivanyos, Hartmut Klauck, Troy Lee, Miklos Santha, Ronald de Wolf

Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2012

2011

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

Troy Lee, Frédéric Magniez, Miklos Santha

CoRR, 2011

The Complexity of Approximate Nash Equilibrium in Congestion Games with Negative Delays.

Frédéric Magniez, Michel de Rougemont, Miklos Santha, Xavier Zeitoun

Proceedings of the Internet and Network Economics - 7th International Workshop, 2011

Improved Bounds for the Randomized Decision Tree Complexity of Recursive Majority.

Frédéric Magniez, Ashwin Nayak, Miklos Santha, David Xiao

Proceedings of the Automata, Languages and Programming - 38th International Colloquium, 2011

2010

Optimal direct sum results for deterministic and randomized decision tree complexity.

Rahul Jain, Hartmut Klauck, Miklos Santha

Inf. Process. Lett., 2010

On the Power of a Unique Quantum Witness.

Rahul Jain, Iordanis Kerenidis, Greg Kuperberg, Miklos Santha, Or Sattath, Shengyu Zhang

Proceedings of the Innovations in Computer Science, 2010

Quantization of Random Walks: Search Algorithms and Hitting Time.

Miklos Santha

Proceedings of the Computer Science, 2010

2009

On the hitting times of quantum versus random walks.

Frédéric Magniez, Ashwin Nayak, Peter C. Richter, Miklos Santha

Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

2008

Quantum Walk Based Search Algorithms.

Miklos Santha

Proceedings of the Theory and Applications of Models of Computation, 2008

Approximate Nash Equilibria for Multi-player Games.

Sébastien Hémon, Michel de Rougemont, Miklos Santha

Proceedings of the Algorithmic Game Theory, First International Symposium, 2008

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

Gábor Ivanyos, Luc Sanselme, Miklos Santha

Proceedings of the LATIN 2008: Theoretical Informatics, 2008

2007

Search via quantum walk.

Frédéric Magniez, Ashwin Nayak, Jérémie Roland, Miklos Santha

Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 2007

An Efficient Quantum Algorithm for the Hidden Subgroup Problem in Extraspecial Groups.

Gábor Ivanyos, Luc Sanselme, Miklos Santha

Proceedings of the STACS 2007, 2007

2006

Locally 2-Dimensional Sperner Problems Complete for the Polynomial Parity Argument Classes.

Katalin Friedl, Gábor Ivanyos, Miklos Santha, Yves F. Verhoeven

Proceedings of the Algorithms and Complexity, 6th Italian Conference, 2006

2005

Efficient testing of groups.

Katalin Friedl, Gábor Ivanyos, Miklos Santha

Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005

Quantum algorithms for the triangle problem.

Frédéric Magniez, Miklos Santha, Mario Szegedy

Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

On the Black-Box Complexity of Sperner's Lemma.

Katalin Friedl, Gábor Ivanyos, Miklos Santha, Yves F. Verhoeven

Proceedings of the Fundamentals of Computation Theory, 15th International Symposium, 2005

2004

Quantum and classical query complexities of local search are polynomially related.

Miklos Santha, Mario Szegedy

Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004

2003

Approximate testing with error relative to input size.

Marcos A. Kiwi, Frédéric Magniez, Miklos Santha

J. Comput. Syst. Sci., 2003

Hidden translation and orbit coset in quantum computing.

Katalin Friedl, Gábor Ivanyos, Frédéric Magniez, Miklos Santha, Pranab Sen

Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

Quantum Testers for Hidden Group Properties.

Katalin Friedl, Frédéric Magniez, Miklos Santha, Pranab Sen

Proceedings of the Mathematical Foundations of Computer Science 2003, 2003

2001

Efficient quantum algorithms for some instances of the non-Abelian hidden subgroup problem.

Gábor Ivanyos, Frédéric Magniez, Miklos Santha

Proceedings of the Thirteenth Annual ACM Symposium on Parallel Algorithms and Architectures, 2001

Quantum Algorithms for Element Distinctness.

Harry Buhrman, Christoph Dürr, Mark Heiligman, Peter Høyer, Frédéric Magniez, Miklos Santha, Ronald de Wolf

Proceedings of the 16th Annual IEEE Conference on Computational Complexity, 2001

2000

Self-testing of universal and fault-tolerant sets of quantum gates.

Wim van Dam, Frédéric Magniez, Michele Mosca, Miklos Santha

Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000

Semantical Counting Circuits.

Fabrice Noilhan, Miklos Santha

Proceedings of the Algorithms and Complexity, 4th Italian Conference, 2000

Exact and Approximate Testing/Correcting of Algebraic Functions: A Survey.

Marcos A. Kiwi, Frédéric Magniez, Miklos Santha

Proceedings of the Theoretical Aspects of Computer Science, 2000

1999

On the Approximation of Finding A(nother) Hamiltonian Cycle in Cubic Hamiltonian Graphs.

Cristina Bazgan, Miklos Santha, Zsolt Tuza

J. Algorithms, 1999

Approximate Testing with Relative Error.

Marcos A. Kiwi, Frédéric Magniez, Miklos Santha

Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

1998

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

Wenceslas Fernandez de la Vega, Alan M. Frieze, Miklos Santha

Algorithmica, 1998

On the Approximation of Finding A(nother) Hamilton Cycle in Cubic Hamilton Graphs (Extended Abstract).

Cristina Bazgan, Miklos Santha, Zsolt Tuza

Proceedings of the STACS 98, 1998

Efficient Approximation Algorithms for the Subset-Sums Equality Problem.

Cristina Bazgan, Miklos Santha, Zsolt Tuza

Proceedings of the Automata, Languages and Programming, 25th International Colloquium, 1998

1996

Oblivious Transfers and Intersecting Codes.

Gilles Brassard, Claude Crépeau, Miklos Santha

IACR Cryptol. ePrint Arch., 1996

A Decision Procedure for Well-Formed Linear Quantum Cellular Automata.

Christoph Dürr, Huong Lê Thanh, Miklos Santha

Proceedings of the STACS 96, 1996

A Decision Procedure for Unitary Linear Quantum Cellular Automata.

Christoph Dürr, Miklos Santha

Proceedings of the 37th Annual Symposium on Foundations of Computer Science, 1996

1994

Verifying the Determinant in Parallel.

Miklos Santha, Sovanna Tan

Proceedings of the Algorithms and Computation, 5th International Symposium, 1994

On the Interactive Complexity of Graph Reliability.

Jean Marc Couveignes, Juan Francisco Díaz-Frías, Michel de Rougemont, Miklos Santha

Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1994

1993

Limiting Negations in Constant Depth Circuits.

Miklos Santha, Christopher B. Wilson

SIAM J. Comput., 1993

Parallel searching of multidimensional cubes.

Miklos Santha, Umesh V. Vazirani

Discret. Math., 1993

A Parallel Reduction of Hamiltonian Cycle to Hamiltonian Path in Tournaments.

Evripidis Bampis, Mohamed El Haddad, Yannis Manoussakis, Miklos Santha

Proceedings of the PARLE '93, 1993

1992

Deciding Bisimilarity is P-Complete.

José L. Balcázar, Joaquim Gabarró, Miklos Santha

Formal Aspects Comput., 1992

1991

Polynomial Size Constant Depth Circuits with a Limited Number of Negations.

Miklos Santha, Christopher B. Wilson

Proceedings of the STACS 91, 1991

Parallel Complexity in the Design and Analysis on Conurrent Systems.

Carme Àlvarez, José L. Balcázar, Joaquim Gabarró, Miklos Santha

Proceedings of the PARLE '91: Parallel Architectures and Languages Europe, 1991

On the Reversibility of Oblivious Transfer.

Claude Crépeau, Miklos Santha

Proceedings of the Advances in Cryptology, 1991

On the Monte Carlo Boolean Decision Tree Complexity of Read-Once Formulae.

Miklos Santha

Proceedings of the Sixth Annual Structure in Complexity Theory Conference, Chicago, Illinois, USA, June 30, 1991

1990

Two Probabilistic Results on Merging.

Wenceslas Fernandez de la Vega, Sampath Kannan, Miklos Santha

Proceedings of the Algorithms, 1990

1987

On Using Deterministic Functions to Reduce Randomness in Probabilistic Algorithms

Miklos Santha

Inf. Comput., September, 1987

Relativized Arthur-Merlin versus Merlin-Arthur Games.

Miklos Santha

Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1987

1986

Generating Quasi-random Sequences from Semi-random Sources.

Miklos Santha, Umesh V. Vazirani

J. Comput. Syst. Sci., 1986

1984

Generating Quasi-Random Sequences from Slightly-Random Sources (Extended Abstract)

Miklos Santha, Umesh V. Vazirani

Proceedings of the 25th Annual Symposium on Foundations of Computer Science, 1984