Miklos Santha

Publication Activity (10 Years)

Years Active: 1984-2024
Publications (10 Years): 53

Top Venues

CoRR

Electron. Colloquium Comput. Complex.

J. Comput. Syst. Sci.

MFCS

Publications

Jonathan Allcock, João F. Doriguello, Gábor Ivanyos, Miklos Santha
Beyond Bell sampling: stabilizer state learning and quantum pseudorandomness lower bounds on qudits. CoRR (2024)
Divesh Aggarwal, Antoine Joux, Miklos Santha, Karol Wegrzycki
Polynomial Time Algorithms for Integer Programming and Unbounded Subset Sum in the Total Regime. CoRR (2024)
Jonathan Allcock, Jinge Bao, João F. Doriguello, Alessandro Luongo, Miklos Santha
Constant-depth circuits for Uniformly Controlled Gates and Boolean functions with application to quantum memory circuits. CoRR (2023)
Jonathan Allcock, Jinge Bao, Aleksandrs Belovs, Troy Lee, Miklos Santha
On the quantum time complexity of divide and conquer. CoRR (2023)
Siyi Yang, Naixu Guo, Miklos Santha, Patrick Rebentrost
Quantum Alphatron: quantum advantage for learning with kernels and noise. Quantum 7 (2023)
João F. Doriguello, Alessandro Luongo, Jinge Bao, Patrick Rebentrost, Miklos Santha
Quantum Algorithm for Stochastic Optimal Stopping Problems with Applications in Finance. TQC (2022)
Jonathan Allcock, Yassine Hamoudi, Antoine Joux, Felix Klingelhöfer, Miklos Santha
Classical and Quantum Algorithms for Variants of Subset-Sum via Dynamic Programming. ESA (2022)
Sevag Gharibian, Miklos Santha, Jamie Sikora, Aarthi Sundaram, Justin Yirka
Quantum generalizations of the polynomial hierarchy with applications to QMA(2). Comput. Complex. 31 (2) (2022)
Serge Massar, Miklos Santha
Total functions in QMA. Quantum Inf. Process. 20 (1) (2021)
Troy Lee, Miklos Santha, Shengyu Zhang
Quantum algorithms for graph problems with cut queries. SODA (2021)
Jonathan Allcock, Yassine Hamoudi, Antoine Joux, Felix Klingelhöfer, Miklos Santha
Classical and quantum dynamic programming for Subset-Sum and variants. CoRR (2021)
Serge Massar, Miklos Santha
Characterising the intersection of QMA and coQMA. Quantum Inf. Process. 20 (12) (2021)
Troy Lee, Tongyang Li, Miklos Santha, Shengyu Zhang
On the Cut Dimension of a Graph. Computational Complexity Conference (2021)
Rahul Jain, Hartmut Klauck, Srijita Kundu, Troy Lee, Miklos Santha, Swagato Sanyal, Jevgenijs Vihrovs
Quadratically Tight Relations for Randomized Query Complexity. Theory Comput. Syst. 64 (1) (2020)
Troy Lee, Tongyang Li, Miklos Santha, Shengyu Zhang
On the cut dimension of a graph. CoRR (2020)
Troy Lee, Miklos Santha, Shengyu Zhang
Quantum algorithms for graph problems with cut queries. CoRR (2020)
Gábor Ivanyos, Antoine Joux, Miklos Santha
Discrete logarithm and Diffie-Hellman problems in identity black-box groups. CoRR (2019)
Troy Lee, Maharshi Ray, Miklos Santha
Strategies for Quantum Races. ITCS (2019)
Yassine Hamoudi, Patrick Rebentrost, Ansis Rosmanis, Miklos Santha
Quantum and classical algorithms for approximate submodular function minimization. Quantum Inf. Comput. 19 (15&16) (2019)
Dmitry Gavinsky, Troy Lee, Miklos Santha, Swagato Sanyal
A Composition Theorem for Randomized Query Complexity via Max-Conflict Complexity. ICALP (2019)
Yassine Hamoudi, Patrick Rebentrost, Ansis Rosmanis, Miklos Santha
Quantum and Classical Algorithms for Approximate Submodular Function Minimization. CoRR (2019)
Gábor Ivanyos, Marek Karpinski, Miklos Santha, Nitin Saxena, Igor E. Shparlinski
Polynomial Interpolation and Identity Testing from High Powers Over Finite Fields. Algorithmica 80 (2) (2018)
Dmitry Gavinsky, Troy Lee, Miklos Santha
On the randomised query complexity of composition. CoRR (2018)
Rahul Jain, Hartmut Klauck, Srijita Kundu, Troy Lee, Miklos Santha, Swagato Sanyal, Jevgenijs Vihrovs
Quadratically Tight Relations for Randomized Query Complexity. CSR (2018)
Gábor Ivanyos, Anupam Prakash, Miklos Santha
On learning linear functions from subset and its applications in quantum computing. CoRR (2018)
Gábor Ivanyos, Anupam Prakash, Miklos Santha
On Learning Linear Functions from Subset and Its Applications in Quantum Computing. ESA (2018)
Gábor Ivanyos, Raghav Kulkarni, Youming Qiao, Miklos Santha, Aarthi Sundaram
On the complexity of trial and error for constraint satisfaction problems. J. Comput. Syst. Sci. 92 (2018)
Sevag Gharibian, Miklos Santha, Jamie Sikora, Aarthi Sundaram, Justin Yirka
Quantum Generalizations of the Polynomial Hierarchy with Applications to QMA(2). MFCS (2018)
Troy Lee, Maharshi Ray, Miklos Santha
Strategies for quantum races. CoRR (2018)
Dmitry Gavinsky, Troy Lee, Miklos Santha, Swagato Sanyal
A composition theorem for randomized query complexity via max conflict complexity. CoRR (2018)
Divesh Aggarwal, Antoine Joux, Anupam Prakash, Miklos Santha
A New Public-Key Cryptosystem via Mersenne Numbers. CRYPTO (3) (2018)
Divesh Aggarwal, Gavin K. Brennen, Troy Lee, Miklos Santha, Marco Tomamichel
Quantum Attacks on Bitcoin, and How to Protect Against Them. Ledger 3 (2018)
Sevag Gharibian, Miklos Santha, Jamie Sikora, Aarthi Sundaram, Justin Yirka
Quantum generalizations of the polynomial hierarchy with applications to QMA(2). CoRR (2018)
Itai Arad, Miklos Santha, Aarthi Sundaram, Shengyu Zhang
Linear-Time Algorithm for Quantum 2SAT. Theory Comput. 14 (1) (2018)
Gábor Ivanyos, Miklos Santha
Solving systems of diagonal polynomial equations over finite fields. Theor. Comput. Sci. 657 (2017)
Dmitry Gavinsky, Rahul Jain, Hartmut Klauck, Srijita Kundu, Troy Lee, Miklos Santha, Swagato Sanyal, Jevgenijs Vihrovs
Quadratically Tight Relations for Randomized Query Complexity. Electron. Colloquium Comput. Complex. 24 (2017)
Troy Lee, Frédéric Magniez, Miklos Santha
Improved Quantum Query Algorithms for Triangle Detection and Associativity Testing. Algorithmica 77 (2) (2017)
Aleksandrs Belovs, Gábor Ivanyos, Youming Qiao, Miklos Santha, Siyi Yang
On the Polynomial Parity Argument Complexity of the Combinatorial Nullstellensatz. Computational Complexity Conference (2017)
Anurag Anshu, Dmitry Gavinsky, Rahul Jain, Srijita Kundu, Troy Lee, Priyanka Mukhopadhyay, Miklos Santha, Swagato Sanyal
A Composition Theorem for Randomized Query Complexity. FSTTCS (2017)
Divesh Aggarwal, Antoine Joux, Anupam Prakash, Miklos Santha
A New Public-Key Cryptosystem via Mersenne Numbers. IACR Cryptol. ePrint Arch. 2017 (2017)
Anurag Anshu, Dmitry Gavinsky, Rahul Jain, Srijita Kundu, Troy Lee, Priyanka Mukhopadhyay, Miklos Santha, Swagato Sanyal
A Composition Theorem for Randomized Query complexity. Electron. Colloquium Comput. Complex. 24 (2017)
Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Troy Lee, Miklos Santha, Juris Smotrovs
Separations in Query Complexity Based on Pointer Functions. J. ACM 64 (5) (2017)
Dmitry Gavinsky, Rahul Jain, Hartmut Klauck, Srijita Kundu, Troy Lee, Miklos Santha, Swagato Sanyal, Jevgenijs Vihrovs
Quadratically Tight Relations for Randomized Query Complexity. CoRR (2017)
Aleksandrs Belovs, Gábor Ivanyos, Youming Qiao, Miklos Santha, Siyi Yang
On the Polynomial Parity Argument Complexity of the Combinatorial Nullstellensatz. CoRR (2017)
Anurag Anshu, Dmitry Gavinsky, Rahul Jain, Srijita Kundu, Troy Lee, Priyanka Mukhopadhyay, Miklos Santha, Swagato Sanyal
A Composition Theorem for Randomized Query Complexity. CoRR (2017)
Anurag Anshu, Aleksandrs Belovs, Shalev Ben-David, Mika Göös, Rahul Jain, Robin Kothari, Troy Lee, Miklos Santha
Separations in communication complexity using cheat sheets and information complexity. Electron. Colloquium Comput. Complex. 23 (2016)
Itai Arad, Miklos Santha, Aarthi Sundaram, Shengyu Zhang
Linear Time Algorithm for Quantum 2SAT. ICALP (2016)
Anurag Anshu, Aleksandrs Belovs, Shalev Ben-David, Mika Göös, Rahul Jain, Robin Kothari, Troy Lee, Miklos Santha
Separations in Communication Complexity Using Cheat Sheets and Information Complexity. FOCS (2016)
Itai Arad, Adam Bouland, Daniel Grier, Miklos Santha, Aarthi Sundaram, Shengyu Zhang
On the Complexity of Probabilistic Trials for Hidden Satisfiability Problems. MFCS (2016)
Frédéric Magniez, Ashwin Nayak, Miklos Santha, Jonah Sherman, Gábor Tardos, David Xiao
Improved bounds for the randomized decision tree Complexity of recursive majority. Random Struct. Algorithms 48 (3) (2016)
Anurag Anshu, Aleksandrs Belovs, Shalev Ben-David, Mika Göös, Rahul Jain, Robin Kothari, Troy Lee, Miklos Santha
Separations in communication complexity using cheat sheets and information complexity. CoRR (2016)
Itai Arad, Adam Bouland, Daniel Grier, Miklos Santha, Aarthi Sundaram, Shengyu Zhang
On the complexity of probabilistic trials for hidden satisfiability problems. CoRR (2016)
Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Troy Lee, Miklos Santha, Juris Smotrovs
Separations in query complexity based on pointer functions. STOC (2016)
Robin Kothari, David Racicot-Desloges, Miklos Santha
Separating Decision Tree Complexity from Subcube Partition Complexity. APPROX-RANDOM (2015)
Gábor Ivanyos, Marek Karpinski, Youming Qiao, Miklos Santha
Generalized Wong sequences and their applications to Edmonds' problems. J. Comput. Syst. Sci. 81 (7) (2015)
Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Troy Lee, Miklos Santha, Juris Smotrovs
Separations in Query Complexity Based on Pointer Functions. Electron. Colloquium Comput. Complex. 22 (2015)
Gábor Ivanyos, Miklos Santha
On Solving Systems of Diagonal Polynomial Equations Over Finite Fields. FAW (2015)
Robin Kothari, David Racicot-Desloges, Miklos Santha
Separating decision tree complexity from subcube partition complexity. CoRR (2015)
Itai Arad, Miklos Santha, Aarthi Sundaram, Shengyu Zhang
Linear time algorithm for quantum 2SAT. CoRR (2015)
Gábor Ivanyos, Marek Karpinski, Miklos Santha, Nitin Saxena, Igor E. Shparlinski
Polynomial Interpolation and Identity Testing from High Powers over Finite Fields. CoRR (2015)
Gábor Ivanyos, Miklos Santha
On solving systems of diagonal polynomial equations over finite fields. CoRR (2015)
Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Troy Lee, Miklos Santha, Juris Smotrovs
Separations in Query Complexity Based on Pointer Functions. CoRR (2015)
Miklos Santha
Quantum and Randomized Query Complexities (Extended Abstract). TAMC (2015)
Gábor Ivanyos, Raghav Kulkarni, Youming Qiao, Miklos Santha, Aarthi Sundaram
On the Complexity of Trial and Error for Constraint Satisfaction Problems. ICALP (1) (2014)
Thomas Decker, Peter Høyer, Gábor Ivanyos, Miklos Santha
Polynomial time quantum algorithms for certain bivariate hidden polynomial problems. Quantum Inf. Comput. 14 (9-10) (2014)
Katalin Friedl, Gábor Ivanyos, Frédéric Magniez, Miklos Santha, Pranab Sen
Hidden Translation and Translating Coset in Quantum Computing. SIAM J. Comput. 43 (1) (2014)
Gábor Ivanyos, Marek Karpinski, Youming Qiao, Miklos Santha
Generalized Wong sequences and their applications to Edmonds' problems. STACS (2014)
Thomas Decker, Gábor Ivanyos, Raghav Kulkarni, Youming Qiao, Miklos Santha
An Efficient Quantum Algorithm for Finding Hidden Parabolic Subgroups in the General Linear Group. MFCS (2) (2014)
Gábor Ivanyos, Raghav Kulkarni, Youming Qiao, Miklos Santha, Aarthi Sundaram
On the complexity of trial and error for constraint satisfaction problems. Electron. Colloquium Comput. Complex. 21 (2014)
Gábor Ivanyos, Raghav Kulkarni, Youming Qiao, Miklos Santha, Aarthi Sundaram
On the Complexity of Trial and Error for Constraint Satisfaction Problems. CoRR (2014)
Gábor Ivanyos, Marek Karpinski, Youming Qiao, Miklos Santha
Generalized Wong sequences and their applications to Edmonds' problems. CoRR (2013)
Gábor Ivanyos, Marek Karpinski, Youming Qiao, Miklos Santha
Generalized Wong sequences and their applications to Edmonds' problems. Electron. Colloquium Comput. Complex. 20 (2013)
Troy Lee, Frédéric Magniez, Miklos Santha
Improved quantum query algorithms for triangle finding and associativity testing. SODA (2013)
Frédéric Magniez, Ashwin Nayak, Miklos Santha, Jonah Sherman, Gábor Tardos, David Xiao
Improved bounds for the randomized decision tree complexity of recursive majority. CoRR (2013)
Raghav Kulkarni, Miklos Santha
Query Complexity of Matroids. CIAC (2013)
Thomas Decker, Gábor Ivanyos, Miklos Santha, Pawel Wocjan
Hidden Symmetry Subgroup Problems. SIAM J. Comput. 42 (5) (2013)
Rahul Jain, Iordanis Kerenidis, Greg Kuperberg, Miklos Santha, Or Sattath, Shengyu Zhang
On the Power of a Unique Quantum Witness. Theory Comput. 8 (1) (2012)
Frédéric Magniez, Ashwin Nayak, Peter C. Richter, Miklos Santha
On the Hitting Times of Quantum Versus Random Walks. Algorithmica 63 (1-2) (2012)
Gábor Ivanyos, Hartmut Klauck, Troy Lee, Miklos Santha, Ronald de Wolf
New bounds on the classical and quantum communication complexity of some graph properties CoRR (2012)
Gábor Ivanyos, Hartmut Klauck, Troy Lee, Miklos Santha, Ronald de Wolf
New bounds on the classical and quantum communication complexity of some graph properties. FSTTCS (2012)
Raghav Kulkarni, Miklos Santha
Query complexity of matroids. Electron. Colloquium Comput. Complex. 19 (2012)
Gábor Ivanyos, Luc Sanselme, Miklos Santha
An Efficient Quantum Algorithm for the Hidden Subgroup Problem in Nil-2 Groups. Algorithmica 62 (1-2) (2012)
Troy Lee, Frédéric Magniez, Miklos Santha
Learning graph based quantum query algorithms for finding constant-size subgraphs. Chic. J. Theor. Comput. Sci. 2012 (2012)
Frédéric Magniez, Ashwin Nayak, Miklos Santha, David Xiao
Improved Bounds for the Randomized Decision Tree Complexity of Recursive Majority. ICALP (1) (2011)
Frédéric Magniez, Michel de Rougemont, Miklos Santha, Xavier Zeitoun
The Complexity of Approximate Nash Equilibrium in Congestion Games with Negative Delays. WINE (2011)
Troy Lee, Frédéric Magniez, Miklos Santha
A learning graph based quantum query algorithm for finding constant-size subgraphs CoRR (2011)
Frédéric Magniez, Ashwin Nayak, Jérémie Roland, Miklos Santha
Search via Quantum Walk. SIAM J. Comput. 40 (1) (2011)
Frédéric Magniez, Michel de Rougemont, Miklos Santha, Xavier Zeitoun
The complexity of approximate Nash equilibrium in congestion games with negative delays CoRR (2011)
Rahul Jain, Hartmut Klauck, Miklos Santha
Optimal Direct Sum Results for Deterministic and Randomized Decision Tree Complexity CoRR (2010)
Rahul Jain, Hartmut Klauck, Miklos Santha
Optimal direct sum results for deterministic and randomized decision tree complexity. Inf. Process. Lett. 110 (20) (2010)
Rahul Jain, Iordanis Kerenidis, Greg Kuperberg, Miklos Santha, Or Sattath, Shengyu Zhang
On the Power of a Unique Quantum Witness. ICS (2010)
Frédéric Magniez, Ashwin Nayak, Miklos Santha, David Xiao
Improved bounds for the randomized decision tree complexity of recursive majority. Electron. Colloquium Comput. Complex. 17 (2010)
Miklos Santha
Quantization of Random Walks: Search Algorithms and Hitting Time. CSR (2010)
Miklos Santha, Mario Szegedy
Quantum and Classical Query Complexities of Local Search Are Polynomially Related. Algorithmica 55 (3) (2009)
Frédéric Magniez, Ashwin Nayak, Peter C. Richter, Miklos Santha
On the hitting times of quantum versus random walks. SODA (2009)
Katalin Friedl, Gábor Ivanyos, Miklos Santha, Yves F. Verhoeven
On the Black-Box Complexity of Sperner's Lemma. Theory Comput. Syst. 45 (3) (2009)
Katalin Friedl, Miklos Santha, Frédéric Magniez, Pranab Sen
Quantum Testers for Hidden Group Properties. Fundam. Informaticae 91 (2) (2009)
Gábor Ivanyos, Luc Sanselme, Miklos Santha
An Efficient Quantum Algorithm for the Hidden Subgroup Problem in Nil-2 Groups. LATIN (2008)
Miklos Santha
Quantum Walk Based Search Algorithms. TAMC (2008)
Miklos Santha
Quantum walk based search algorithms CoRR (2008)

Miklos Santha.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Miklos Santha