Longest common subsequence (LCS) and edit distance (ED) are fundamental similarity measures of interest to genomic applications (insertions/deletions/substitutions are a [...]

I’m excited to share the news of two upcoming workshops…   TCS Early Career Mentoring Workshop Yael Kalai, Matt Weinberg, and I are organizing a TCS mentoring [...]

For the past few months, we, the STOC 2019 PC, have enjoyed the privilege of reading and discussing a lot of exciting submissions. On Sunday and Monday we will reject most of [...]

Manolis Zampetakis and I are organizing a workshop at FOCS on the complexity of total search problems. Looking for a needle that you know is in the haystack Search [...]

I was excited to see “Approximating Edit Distance Within Constant Factor in Truly Sub-Quadratic Time” by Chakraborty, Das, Goldenberg, Koucky, and Saks in this [...]

In a new paper with Mika Goos, we prove an lower bound on the randomized communication complexity of computing an approximate Nash equilibrium in a two-player game. Then [...]