Miklos Santha

According to our database, Miklos Santha authored at least 95 papers between 1984 and 2024.

Collaborative distances:

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

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

On the quantum time complexity of divide and conquer.

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

CoRR, 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 generalizations of the polynomial hierarchy with applications to QMA(2).

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

Comput. Complex., 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

2020

Quadratically Tight Relations for Randomized Query Complexity.

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

Theory Comput. Syst., 2020

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

Linear-Time Algorithm for Quantum 2SAT.

Itai Arad, Miklos Santha, Aarthi Sundaram, Shengyu Zhang

Theory Comput., 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 complexity of trial and error for constraint satisfaction problems.

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

J. Comput. Syst. Sci., 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

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

2017

Solving systems of diagonal polynomial equations over finite fields.

Gábor Ivanyos, Miklos Santha

Theor. Comput. Sci., 2017

A New Public-Key Cryptosystem via Mersenne Numbers.

Divesh Aggarwal, Antoine Joux, Anupam Prakash, Miklos Santha

IACR Cryptol. ePrint Arch., 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

A Composition Theorem for Randomized Query complexity.

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

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

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 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

Electron. Colloquium Comput. Complex., 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

2015

Generalized Wong sequences and their applications to Edmonds' problems.

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

J. Comput. Syst. Sci., 2015

Separations in Query Complexity Based on Pointer Functions.

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

Electron. Colloquium Comput. Complex., 2015

Quantum and Randomized Query Complexities (Extended Abstract).

Miklos Santha

Proceedings of the Theory and Applications of Models of Computation, 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

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

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

2012

On the Power of a Unique Quantum Witness.

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

Theory Comput., 2012

Query complexity of matroids.

Raghav Kulkarni, Miklos Santha

Electron. Colloquium Comput. Complex., 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

On the Hitting Times of Quantum Versus Random Walks.

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

Algorithmica, 2012

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

Gábor Ivanyos, Luc Sanselme, Miklos Santha

Algorithmica, 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

Search via Quantum Walk.

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

SIAM J. Comput., 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

2010

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

Rahul Jain, Hartmut Klauck, Miklos Santha

Inf. Process. Lett., 2010

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

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

Electron. Colloquium Comput. Complex., 2010

Quantization of Random Walks: Search Algorithms and Hitting Time.

Miklos Santha

Proceedings of the Computer Science, 2010

2009

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

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

Theory Comput. Syst., 2009

Quantum Testers for Hidden Group Properties.

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

Fundam. Informaticae, 2009

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

Miklos Santha, Mario Szegedy

Algorithmica, 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

2007

Quantum Algorithms for the Triangle Problem.

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

SIAM J. Comput., 2007

Self-Testing of Universal and Fault-Tolerant Sets of Quantum Gates.

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

SIAM J. Comput., 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

Quantum Algorithms for Element Distinctness.

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

SIAM J. Comput., 2005

Efficient testing of groups.

Katalin Friedl, Gábor Ivanyos, Miklos Santha

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

2003

Semantical Counting Circuits.

Fabrice Noilhan, Miklos Santha

Theory Comput. Syst., 2003

Approximate testing with error relative to input size.

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

J. Comput. Syst. Sci., 2003

Efficient Quantum Algorithms For Some Instances Of The Non-Abelian Hidden Subgroup Problem.

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

Int. J. Found. Comput. 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

2002

A Decision Procedure for Unitary Linear Quantum Cellular Automata.

Christoph Dürr, Miklos Santha

SIAM J. Comput., 2002

Efficient Approximation Algorithms for the SUBSET-SUMS EQUALITY Problem.

Cristina Bazgan, Miklos Santha, Zsolt Tuza

J. Comput. Syst. Sci., 2002

2001

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

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

Electron. Colloquium Comput. Complex., 2001

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

Verifying the Determinant in Parallel.

Miklos Santha, Sovanna Tan

Comput. Complex., 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

1997

A decision procedure for well-formed linear quantum cellular automata.

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

Random Struct. Algorithms, 1997

1996

Oblivious transfers and intersecting codes.

Gilles Brassard, Claude Crépeau, Miklos Santha

IEEE Trans. Inf. Theory, 1996

1995

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

Miklos Santha

Random Struct. Algorithms, 1995

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

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

J. Algorithms, 1995

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

Two Probabilistic Results on Merging.

Wenceslas Fernandez de la Vega, Sampath Kannan, Miklos Santha

SIAM J. Comput., 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

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

1989

Relativized Arthur-Merlin versus Merlin-Arthur Games

Miklos Santha

Inf. Comput., January, 1989

1987

On Using Deterministic Functions to Reduce Randomness in Probabilistic Algorithms

Miklos Santha

Inf. Comput., September, 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