[Csdmsemo] Theoretical Computer Science/Discrete Math Seminars--Week of February 4, 2019

[Kristina Phillips]

INSTITUTE FOR ADVANCED STUDY

School of Mathematics

Princeton, NJ 08540

 

Theoretical Computer Science/Discrete Math Seminars

Week of February 4, 2019

 

 

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

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

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

 

Monday, February 4

 

Computer Science/Discrete Mathematics Seminar I

Topic:                    Near-Optimal Strong Dispersers

Speaker:              Dean Doron, The University of Texas at Austin

Time/Room:       11:00am - 12:00pm/Simonyi Hall 101

Abstract Link:      <http://www.math.ias.edu/seminars/abstract?event=128894>
http://www.math.ias.edu/seminars/abstract?event=128894

 

 

 

Monday, February 4

 

Seminar on Theoretical Machine Learning

Topic:                    TBA

Speaker:              TBA

Time/Room:       12:15pm - 1:45pm/Princeton University

 

 

 

 

Tuesday, February 5

 

Computer Science/Discrete Mathematics Seminar II

Topic:                    Non-commutative rank

Speaker:              Visu Makam, University of Michigan; Member, School of
Mathematics

Time/Room:       10:30am - 12:30pm/Simonyi Hall 101

Abstract Link:      <http://www.math.ias.edu/seminars/abstract?event=129130>
http://www.math.ias.edu/seminars/abstract?event=129130

 

 

 

1 Near-Optimal Strong Dispersers 
   Dean Doron 



Randomness dispersers are an important tool in the theory of
pseudorandomness, with numerous applications. In this talk, we will consider
one-bit strong dispersers and show their connection to erasure
list-decodable codes and Ramsey graphs. 

The construction I will show achieves near-optimal seed-length and
near-optimal entropy-loss. Viewed as an error-correcting code, we get a
binary code with rate approaching $\varepsilon$ that can be list-decoded
from $1-\varepsilon$ fraction of erasures. This is the first construction to
break the $\varepsilon^2$ rate barrier, solving a long-standing open problem
raised by Guruswami and Indyk.

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




2 Non-commutative rank 
   Visu Makam 



A linear matrix is a matrix whose entries are linear forms in some
indeterminates $t_1,\dots, t_m$ with coefficients in some field $F$. The
commutative rank of a linear matrix is obtained by interpreting it as a
matrix with entries in the function field $F(t_1,\dots,t_m)$, and is
directly related to the central PIT (polynomial identity testing) problem.
The non-commutative rank of a linear matrix is obtained by interpreting it
as a matrix with entries over the free skew field. The non-commutative rank
could be larger than the commutative rank. Many incarnations and
applications of non-commutative rank across areas of math, physics and CS
have been found, some recently, and there is scope for more. 

In this talk, I will discuss several interesting structural and algorithmic
aspects of non-commutative rank, as well as the role it plays in
non-commutative rational identity testing and tensor rank lower bounds. Time
permitting, I will indicate the connections to invariant theory for quivers,
operator scaling and Brascamp--Lieb inequalities. 

No special background beyond standard linear algebra will be assumed.

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

 

 



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

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

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://imap.math.ias.edu/pipermail/csdmsemo/attachments/20190130/48fcb6cd/attachment.html>