225 citations · 582 across the 52 of their papers we have counts for
5 papers · 1 filter
Polynomial Time Algorithms for Integer Programming and Unbounded Subset Sum in the Total Regime
Divesh Aggarwal, Antoine Joux, Miklos Santha +1
The Unbounded Subset Sum (USS) problem is an NP-hard computational problem where the goal is to decide whether there exist non-negative integers such that $x_1 a…
Quantum algorithms for graph problems with cut queries
Troy Lee, Miklos Santha, Shengyu Zhang
Let be an -vertex graph with edges. When asked a subset of vertices, a cut query on returns the number of edges of that have exactly one endpoint in . We…
Quantum and Classical Algorithms for Approximate Submodular Function Minimization
Yassine Hamoudi, Patrick Rebentrost, Ansis Rosmanis +1
Submodular functions are set functions mapping every subset of some ground set of size into the real numbers and satisfying the diminishing returns property. Submodular minimiz…
Improved bounds for the randomized decision tree complexity of recursive majority
Frederic Magniez, Ashwin Nayak, Miklos Santha +3
We consider the randomized decision tree complexity of the recursive 3-majority function. We prove a lower bound of for the two-sided-error randomized dec…
A decision procedure for well-formed linear quantum cellular automata
Christoph Durr, Huong LeThanh, Miklos Santha
In this paper we introduce a new quantum computation model, the linear quantum cellular automaton. Well-formedness is an essential property for any quantum computing device since i…