[iasmath-seminars] Theoretical Computer Science/Discrete Math Seminars- Title and abstract added to Tuesday, March 5

[Kristina Phillips]

INSTITUTE FOR ADVANCED STUDY

School of Mathematics

Princeton, NJ 08540

 

Theoretical Computer Science/Discrete Math Seminars

Week of March 4, 2019

 

 

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

REMINDER: CSDM Seminars will be held in the West Building Lecture Hall 

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

 

Monday, March 4

 

Computer Science/Discrete Mathematics Seminar I

Topic:                    Local and global expansion of graphs

Speaker:              Yuval Peled, New York University

Time/Room:       11:00am - 12:00pm/West Building Lecture Hall

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

 

 

 

Monday, March 4

 

Seminar on Theoretical Machine Learning

Topic:                    FFJORD: Free-form Continuous Dynamics for Scalable
Reversible Generative Models

Speaker:              Will Grathwohl, University of Toronto

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

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

 

 

 

Tuesday, March 5

 

Computer Science/Discrete Mathematics Seminar II

Topic:                    Improved List-Decoding and Local List-Decoding
Algorithms for Polynomial Codes

Speaker:              Swastik Kopparty, Rutgers University; Member, School
of Mathematics

Time/Room:       10:30am - 12:30pm/West Building Lecture Hall

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

 

1 Local and global expansion of graphs 
   Yuval Peled 




The emerging theory of High-Dimensional Expansion suggests a number of
inherently different notions to quantify expansion of simplicial complexes.
We will talk about the notion of local spectral expansion, that plays a key
role in recent advances in PCP theory, coding theory and counting
complexity. Our focus is on bounded-degree complexes, where the problems can
be stated in a graph-theoretic language: 

Let $G$ be a graph. For a vertex $v \in G$, we denote by $G_v$ the subgraph
of $G $ that is induced by the neighbors of $v$. We say that $G$ is
$(a,b)$-regular if (I) $G$ is $a$-regular and (II) $G_v$ is $b$-regular for
every vertex $v$. We analyse the spectral expansion of $(a,b)$-regular
graphs: 

What is the largest spectral gap in the adjacency operator of an
$(a,b)$-regular graph $G$? What is the relation between the local expansion
of the graphs ${G_v : v \in G}$ and the global expansion of $G$? We will
also present a new construction of $(a,b)$-regular local-and-global
expanders. 

Joint work with Michael Chapman and Nati Linial.

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

2 FFJORD: Free-form Continuous Dynamics for Scalable Reversible Generative
Models 
   Will Grathwohl 




A promising class of generative models maps points from a simple
distribution to a complex distribution through an invertible neural network.
Likelihood-based training of these models requires restricting their
architectures to allow cheap computation of Jacobian determinants.
Alternatively, the Jacobian trace can be used if the transformation is
specified by an ordinary differential equation. In this paper, we use
Hutchinson's trace estimator to give a scalable unbiased estimate of the
log-density. The result is a continuous-time invertible generative model
with unbiased density estimation and one-pass sampling, while allowing
unrestricted neural network architectures. We demonstrate our approach on
high-dimensional density estimation, image generation, and variational
inference, achieving the state-of-the-art among exact likelihood methods
with efficient sampling.

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

3 Improved List-Decoding and Local List-Decoding Algorithms for Polynomial
Codes 
   Swastik Kopparty 




I will talk about a recent result showing that some well-studied
polynomial-based error-correcting codes (Folded Reed-Solomon Codes and
Multiplicity Codes) are "list-decodable upto capacity with constant
list-size". 

At its core, this is a statement about questions of the form: "Given some
points in the plane, how many low degree univariate polynomials are such
that their graphs pass through 10% of these points"? 

This leads to list-decodable and locally list-decodable error-correcting
codes with the best known parameters. 

Based on joint work with Noga Ron-Zewi, Shubhangi Saraf and Mary Wootters.

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

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/iasmathsemo/attachments/20190304/ad8cdc81/attachment.html>