[iasmath-semru] [math-ias] Computer Science/Discrete Mathematics Seminar--Week of April 9, 2018

[Kristina Phillips]

INSTITUTE FOR ADVANCED STUDY
School of Mathematics
Princeton, NJ 08540
 
Theoretical Computer Science/Discrete Math Seminars
Week of April 9, 2018
 
***Please note: The April 9th and 10th CSDM Seminars will be held in the
West Building Lecture Hall.*** 
--------------
To view mathematics in titles and abstracts, please click on the talk's
link.
--------------
 
Monday, April 9
 
Computer Science/Discrete Mathematics Seminar I
Topic:                     To Be Announced
Speaker:                 Eyal Lubetzky, New York University
Time/Room:           11:00am - 12:15pm/West Building Lecture Hall
 
 
 
 
Tuesday, April 10
 
Computer Science/Discrete Mathematics Seminar II
Topic:                     Explicit Binary Tree Codes with Polylogarithmic
Size Alphabet
Speaker:                 Gil Cohen, Princeton University
Time/Room:           10:30am - 12:30pm/West Building Lecture Hall
Abstract Link:
http://www.math.ias.edu/seminars/abstract?event=129076
 
 
 

1 Explicit Binary Tree Codes with Polylogarithmic Size Alphabet 
   Gil Cohen 

In this talk, we consider the problem of explicitly constructing a binary
tree code with constant distance and constant alphabet size. We present an
explicit binary tree code with constant distance and alphabet size
polylog(n), where n is the depth of the tree. This is the first improvement
over a two-decade-old construction that has an exponentially larger alphabet
of size poly(n). For analyzing our construction, we prove a bound on the
number of integral roots a real polynomial can have in terms of its sparsity
with respect to the Newton basis - a result of independent interest.
 
Joint work with Bernhard Haeupler and Leonard Schulman.

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




 

 

----------------------------------------------

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

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

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://imap.math.ias.edu/pipermail/iasmathsemrutgers/attachments/20180403/870b4733/attachment.html>