22 citations · 35 across the 10 of their papers we have counts for
4 papers · 1 filter
Approximate Online Pattern Matching in Sub-linear Time
Diptarka Chakraborty, Debarati Das, Michal Koucky
We consider the approximate pattern matching problem under edit distance. In this problem we are given a pattern of length and a text of length over some alphabet $…
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…
Improved bounds on Fourier entropy and Min-entropy
Srinivasan Arunachalam, Sourav Chakraborty, Michal Koucký +2
Given a Boolean function , the Fourier distribution assigns probability to . The Fourier Entropy-Influence (FEI) conjec…
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…