Michael Saks
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Michael Saks has a total of 72 co-authors. Here are the top co-authors by number of shared publications:
- Nathan Linial
The Hebrew University of Jerusalem
6 shared publications - Michal Koucký
Charles University, Prague, Czech Republic
4 shared publications - Justin Gilmer
Department of Mathematics Rutgers University Piscataway NJ USA
3 shared publications - Srikanth Srinivasan
University of Copenhagen, Copenhagen, Denmark
3 shared publications - Amit Daniely
Department of Mathematics Hebrew University 91904 Jerusalem Israel
2 shared publications Jan Bulánek
Faculty of Mathematics and Physics Charles University Prague
2 shared publications
Latest Publications
- Open Access
- 9 June 2026
- Published by Association for Computing Machinery (ACM)
- p. 1338-1343
The Natural Proofs Barrier against Data-Structure Lower-Bounds
- 9 June 2026
- Published by Association for Computing Machinery (ACM)
- p. 1338-1343
Open AccessThe Natural Proofs Barrier against Data-Structure Lower-Bounds
- Open Access
Local Enumeration: The Not-All-Equal Case
Gurumukhani et al. (CCC'24) proposed the local enumeration problem Enum(k, t) as an approach to break the Super Strong Exponential Time Hypothesis (SSETH): for a natural number $k$ and a parameter $t$, given an $n$-variate $k$-CNF with no satisfying assignment of Hamming weight less than $t(n)$, enumerate all satisfying assignments of Hamming weight exactly $t(n)$. Furthermore, they gave a randomized algorithm for Enum(k, t) and employed new ideas to analyze the first non-trivial case, namely $k = 3$. In particular, they solved Enum(3, n/2) in expected $1.598^n$ time. A simple construction shows a lower bound of $6^{\frac{n}{4}} \approx 1.565^n$. In this paper, we show that to break SSETH, it is sufficient to consider a simpler local enumeration problem NAE-Enum(k, t): for a natural number $k$ and a parameter $t$, given an $n$-variate $k$-CNF with no satisfying assignment of Hamming weight less than $t(n)$, enumerate all Not-All-Equal (NAE) solutions of Hamming weight exactly $t(n)$, i.e., those that satisfy and falsify some literal in every clause. We refine the algorithm of Gurumukhani et al. and show that it optimally solves NAE-Enum(3, n/2), namely, in expected time $poly(n) \cdot 6^{\frac{n}{4}}$.Open AccessLocal Enumeration: The Not-All-Equal Case
Gurumukhani et al. (CCC'24) proposed the local enumeration problem Enum(k, t) as an approach to break the Super Strong Exponential Time Hypothesis (SSETH): for a natural number $k$ and a parameter $t$, given an $n$-variate $k$-CNF with no satisfying assignment of Hamming weight less than $t(n)$, enumerate all satisfying assignments of Hamming weight exactly $t(n)$. Furthermore, they gave a randomized algorithm for Enum(k, t) and employed new ideas to analyze the first non-trivial case, namely $k = 3$. In particular, they solved Enum(3, n/2) in expected $1.598^n$ time. A simple construction shows a lower bound of $6^{\frac{n}{4}} \approx 1.565^n$. In this paper, we show that to break SSETH, it is sufficient to consider a simpler local enumeration problem NAE-Enum(k, t): for a natural number $k$ and a parameter $t$, given an $n$-variate $k$-CNF with no satisfying assignment of Hamming weight less than $t(n)$, enumerate all Not-All-Equal (NAE) solutions of Hamming weight exactly $t(n)$, i.e., those that satisfy and falsify some literal in every clause. We refine the algorithm of Gurumukhani et al. and show that it optimally solves NAE-Enum(3, n/2), namely, in expected time $poly(n) \cdot 6^{\frac{n}{4}}$. - Open Access
- 10 June 2024
- Published by Association for Computing Machinery (ACM)
- p. 956-967
Almost Linear Size Edit Distance Sketch
We design an almost linear-size sketching scheme for computing edit distance up to a given threshold k. The scheme consists of two algorithms, a sketching algorithm and a recovery algorithm. The sketching algorithm depends on the parameter k and takes as input a string x and a public random string ρ and computes a sketch skρ(x;k), which is a compressed version of x. The recovery algorithm is given two sketches skρ(x;k) and skρ(y;k) as well as the public random string ρ used to create the two sketches, and (with high probability) if the edit distance ED(x,y) between x and y is at most k, will output ED(x,y) together with an optimal sequence of edit operations that transforms x to y, and if ED(x,y) > k will output large. The size of the sketch output by the sketching algorithm on input x is k2O(√log(n)loglog(n)) (where n is an upper bound on length of x). The sketching and recovery algorithms both run in time polynomial in n. The dependence of sketch size on k is information theoretically optimal and improves over the quadratic dependence on k in schemes of Kociumaka, Porat and Starikovskaya (FOCS’2021), and Bhattacharya and Koucký (STOC’2023).
- 10 June 2024
- Published by Association for Computing Machinery (ACM)
- p. 956-967
Open AccessAlmost Linear Size Edit Distance Sketch
We design an almost linear-size sketching scheme for computing edit distance up to a given threshold k. The scheme consists of two algorithms, a sketching algorithm and a recovery algorithm. The sketching algorithm depends on the parameter k and takes as input a string x and a public random string ρ and computes a sketch skρ(x;k), which is a compressed version of x. The recovery algorithm is given two sketches skρ(x;k) and skρ(y;k) as well as the public random string ρ used to create the two sketches, and (with high probability) if the edit distance ED(x,y) between x and y is at most k, will output ED(x,y) together with an optimal sequence of edit operations that transforms x to y, and if ED(x,y) > k will output large. The size of the sketch output by the sketching algorithm on input x is k2O(√log(n)loglog(n)) (where n is an upper bound on length of x). The sketching and recovery algorithms both run in time polynomial in n. The dependence of sketch size on k is information theoretically optimal and improves over the quadratic dependence on k in schemes of Kociumaka, Porat and Starikovskaya (FOCS’2021), and Bhattacharya and Koucký (STOC’2023).
- Open Access
On the rational relationships among pseudo-roots of a non-commutative polynomial
For a non-commutative ring R, we consider factorizations of polynomials in R[t] where t is a central variable. A pseudo-root of a polynomial p(t) is an element x in R, for which there exist polynomials q(t) and s(t) such that p(t)=q(t)(t-x)s(t). We investigate the rational relationships that hold among the pseudo-roots of p(t) by using the diamond operations for cover graphs of modular lattices.
Open AccessOn the rational relationships among pseudo-roots of a non-commutative polynomial
For a non-commutative ring R, we consider factorizations of polynomials in R[t] where t is a central variable. A pseudo-root of a polynomial p(t) is an element x in R, for which there exist polynomials q(t) and s(t) such that p(t)=q(t)(t-x)s(t). We investigate the rational relationships that hold among the pseudo-roots of p(t) by using the diamond operations for cover graphs of modular lattices.
- 4 March 2020
- Published by Springer Nature in Combinatorica
- Vol. 40 (2) , 237-244
An Asymptotically Tight Bound on the Number of Relevant Variables in a Bounded Degree Boolean function
- 4 March 2020
- Published by Springer Nature in Combinatorica
- Vol. 40 (2) , 237-244
An Asymptotically Tight Bound on the Number of Relevant Variables in a Bounded Degree Boolean function
- Open Access
An Asymptotically Tight Bound on the Number of Relevant Variables in a Bounded Degree Boolean Function
We prove that there is a constant $C\leq 6.614$ such that every Boolean function of degree at most $d$ (as a polynomial over $\mathbb{R}$) is a $C\cdot 2^d$-junta, i.e. it depends on at most $C\cdot 2^d$ variables. This improves the $d\cdot 2^{d-1}$ upper bound of Nisan and Szegedy [Computational Complexity 4 (1994)]. Our proof uses a new weighting scheme where we assign weights to variables based on the highest degree monomial they appear on. The bound of $C\cdot 2^d$ is tight up to the constant $C$ as a lower bound of $2^d-1$ is achieved by a read-once decision tree of depth $d$. We slightly improve the lower bound by constructing, for each positive integer $d$, a function of degree $d$ with $3\cdot 2^{d-1}-2$ relevant variables. A similar construction was independently observed by Shinkar and Tal.Open AccessAn Asymptotically Tight Bound on the Number of Relevant Variables in a Bounded Degree Boolean Function
We prove that there is a constant $C\leq 6.614$ such that every Boolean function of degree at most $d$ (as a polynomial over $\mathbb{R}$) is a $C\cdot 2^d$-junta, i.e. it depends on at most $C\cdot 2^d$ variables. This improves the $d\cdot 2^{d-1}$ upper bound of Nisan and Szegedy [Computational Complexity 4 (1994)]. Our proof uses a new weighting scheme where we assign weights to variables based on the highest degree monomial they appear on. The bound of $C\cdot 2^d$ is tight up to the constant $C$ as a lower bound of $2^d-1$ is achieved by a read-once decision tree of depth $d$. We slightly improve the lower bound by constructing, for each positive integer $d$, a function of degree $d$ with $3\cdot 2^{d-1}-2$ relevant variables. A similar construction was independently observed by Shinkar and Tal. - 25 April 2018
- Published by Springer Nature
- p. 23-28
Online Labeling: Algorithms, Lower Bounds and Open Questions
- 25 April 2018
- Published by Springer Nature
- p. 23-28
Online Labeling: Algorithms, Lower Bounds and Open Questions
- Open Access
Towards an algebraic natural proofs barrier via polynomial identity testing
We observe that a certain kind of algebraic proof - which covers essentially all known algebraic circuit lower bounds to date - cannot be used to prove lower bounds against VP if and only if what we call succinct hitting sets exist for VP. This is analogous to the Razborov-Rudich natural proofs barrier in Boolean circuit complexity, in that we rule out a large class of lower bound techniques under a derandomization assumption. We also discuss connections between this algebraic natural proofs barrier, geometric complexity theory, and (algebraic) proof complexity.
Open AccessTowards an algebraic natural proofs barrier via polynomial identity testing
We observe that a certain kind of algebraic proof - which covers essentially all known algebraic circuit lower bounds to date - cannot be used to prove lower bounds against VP if and only if what we call succinct hitting sets exist for VP. This is analogous to the Razborov-Rudich natural proofs barrier in Boolean circuit complexity, in that we rule out a large class of lower bound techniques under a derandomization assumption. We also discuss connections between this algebraic natural proofs barrier, geometric complexity theory, and (algebraic) proof complexity.
- Open Access
Noisy population recovery in polynomial time
In the noisy population recovery problem of Dvir et al., the goal is to learn an unknown distribution $f$ on binary strings of length $n$ from noisy samples. For some parameter $\mu \in [0,1]$, a noisy sample is generated by flipping each coordinate of a sample from $f$ independently with probability $(1-\mu)/2$. We assume an upper bound $k$ on the size of the support of the distribution, and the goal is to estimate the probability of any string to within some given error $\varepsilon$. It is known that the algorithmic complexity and sample complexity of this problem are polynomially related to each other. We show that for $\mu > 0$, the sample complexity (and hence the algorithmic complexity) is bounded by a polynomial in $k$, $n$ and $1/\varepsilon$ improving upon the previous best result of $\mathsf{poly}(k^{\log\log k},n,1/\varepsilon)$ due to Lovett and Zhang. Our proof combines ideas from Lovett and Zhang with a \emph{noise attenuated} version of M\"{o}bius inversion. In turn, the latter crucially uses the construction of \emph{robust local inverse} due to Moitra and Saks.Open AccessNoisy population recovery in polynomial time
In the noisy population recovery problem of Dvir et al., the goal is to learn an unknown distribution $f$ on binary strings of length $n$ from noisy samples. For some parameter $\mu \in [0,1]$, a noisy sample is generated by flipping each coordinate of a sample from $f$ independently with probability $(1-\mu)/2$. We assume an upper bound $k$ on the size of the support of the distribution, and the goal is to estimate the probability of any string to within some given error $\varepsilon$. It is known that the algorithmic complexity and sample complexity of this problem are polynomially related to each other. We show that for $\mu > 0$, the sample complexity (and hence the algorithmic complexity) is bounded by a polynomial in $k$, $n$ and $1/\varepsilon$ improving upon the previous best result of $\mathsf{poly}(k^{\log\log k},n,1/\varepsilon)$ due to Lovett and Zhang. Our proof combines ideas from Lovett and Zhang with a \emph{noise attenuated} version of M\"{o}bius inversion. In turn, the latter crucially uses the construction of \emph{robust local inverse} due to Moitra and Saks.