[iasmath-seminars] Theoretical Computer Science/Discrete Math Seminars -- Week of November 6, 2017

[Anthony Pulido]

INSTITUTE FOR ADVANCED STUDY
School of Mathematics
Princeton, NJ 08540

Theoretical Computer Science/Discrete Math Seminars
Week of November 6, 2017


*****Please note that next week's CSDM seminars will take place in the West Building Lecture Hall, on account of the week-long workshop being held in S-101.

--------------
To view mathematics in titles and abstracts, please click on the talk's link.
--------------

Monday, November 6

Computer Science/Discrete Mathematics Seminar I
Topic: 		Language edit distance, $(\min,+)$-matrix multiplication & beyond
Speaker: 	Barna Saha, University of Massachusetts, Amherst
Time/Room: 	11:00am - 12:15pm/West Building Lecture Hall
Abstract Link:	http://www.math.ias.edu/seminars/abstract?event=128787



Tuesday, November 7

Computer Science/Discrete Mathematics Seminar II
Topic: 		Pseudorandom generators for unordered branching programs
Speaker: 	Eshan Chattopadhyay, Member, School of Mathematics
Time/Room: 	10:30am - 12:30pm/West Building Lecture Hall
Abstract Link:	http://www.math.ias.edu/seminars/abstract?event=129025

1 Language edit distance, $(\min,+)$-matrix multiplication & beyond
    Barna Saha

The language edit distance is a significant generalization of two basic 
problems in computer science: parsing and string edit distance 
computation. Given any context free grammar, it computes the minimum 
number of insertions, deletions and substitutions required to convert a 
given input string into a valid member of the language. In 1972, Aho and 
Peterson gave a dynamic programming algorithm that solves this problem 
in time cubic in the string length. Despite its vast number of 
applications, in forty years there has been no improvement over this 
running time.

Computing $(\min,+)$-product of two n by n matrices in truly subcubic 
time is an outstanding open question, as it is equivalent to the famous 
All-Pairs-Shortest-Paths problem. Even when matrices have entries 
bounded in $[1,n]$, obtaining a truly subcubic $(\min,+)$-product 
algorithm will be a major breakthrough in computer science.

In this presentation, I will explore the connection between these two 
problems which led us to develop the first truly subcubic algorithms for 
the following problems with improvements coming for each of these 
problems after several decades: (1) language edit distance, (2) 
RNA-folding-a basic computational biology problem and a special case of 
language edit distance computation, (3) stochastic grammar 
parsing—fundamental to natural language processing, and (4) 
$(\min,+)$-product of integer matrices with entries bounded in 
$n^{3-\omega-c}$ where $c > 0$ is any constant and, $\omega$ is the 
exponent of the fast matrix multiplication, widely believed to be 2.

Time permitting, we will also discuss developing highly efficient linear 
time approximation algorithms for language edit distance for important 
subclasses of context free grammars.

http://www.math.ias.edu/seminars/abstract?event=128787

2 Pseudorandom generators for unordered branching programs
    Eshan Chattopadhyay

We present an explicit pseudorandom generator with seed length 
$\tilde{O}((\log n)^{w+1})$ for read-once, oblivious, width $w$ 
branching programs that can read their input bits in any order. This 
improves upon the work of Impaggliazzo, Meka and Zuckerman where they 
required seed length $n^{1/2+o(1)}$.

A central ingredient in our work is the following bound that we prove on 
the Fourier spectrum of branching programs. For any width $w$ 
(read-once, oblivious) branching program $B:\{0,1\}^n\rightarrow 
\{0,1\}$, any $k \in \{1,\ldots,n\}$, \[\sum_{S: |S|=k}|\widehat{B}(S)| 
\le O((\log n)^{wk}).\] This settles a conjecture posed by Reingold, 
Steinke, and Vadhan.

(Based on joint work with Pooya Hatami, Omer Reingold, and Avishay Tal.)

http://www.math.ias.edu/seminars/abstract?event=129025

Computer Science/Discrete Math Seminars can be found on our web page:

http://www.math.ias.edu/csdm
http://www.math.ias.edu