22 citations · 99 across the 20 of their papers we have counts for
23 papers
Concentration from Product Moments via an Additional Element of Randomness
Michael Saks, Aravind Srinivasan, Renata Valieva
The standard method of exponential moments for proving concentration bounds can often be replaced by an argument based on elementary symmetric polynomials. We introduce an addition…
On the rational relationships among pseudo-roots of a non-commutative polynomial
Vladimir Retakh, Michael Saks
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 th…
Constant factor approximations to edit distance on far input pairs in nearly linear time
Michal Koucký, Michael E. Saks
For any , there are constants and and a randomized algorithm that takes as input an integer and two strings of length at most , an…
Approximating Edit Distance Within Constant Factor in Truly Sub-Quadratic Time
Diptarka Chakraborty, Debarati Das, Elazar Goldenberg +2
Edit distance is a measure of similarity of two strings based on the minimum number of character insertions, deletions, and substitutions required to transform one string into the…
On the Discrepancy of Random Matrices with Many Columns
Cole Franks, Michael Saks
Motivated by the Komlós conjecture in combinatorial discrepancy, we study the discrepancy of random matrices with rows and independent columns drawn from a bounded lattice…
Lower bounds for Combinatorial Algorithms for Boolean Matrix Multiplication
Debarati Das, Michal Koucký, Michael Saks
In this paper we propose models of combinatorial algorithms for the Boolean Matrix Multiplication (BMM), and prove lower bounds on computing BMM in these models. First, we give a r…