22 citations · 99 across the 20 of their papers we have counts for
4 papers · 1 filter
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…
An Asymptotically Tight Bound on the Number of Relevant Variables in a Bounded Degree Boolean Function
John Chiarelli, Pooya Hatami, Michael Saks
We prove that there is a constant such that every Boolean function of degree at most (as a polynomial over ) is a -junta, i.e. it depends…