[Csdmsemo] Theoretical Computer Science/Discrete Math Seminars--New start time for Monday CSDM Seminars

[Kristina Phillips]

INSTITUTE FOR ADVANCED STUDY

School of Mathematics

Princeton, NJ 08540

 

Theoretical Computer Science/Discrete Math Seminars

Week of January 28, 2019

 

 

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

***Please Note***

The Monday CSDM Seminars will now begin at 11:00AM. 

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

 

Monday, January 28

 

Computer Science/Discrete Mathematics Seminar I

Topic:                    PCP and Delegating Computation: A Love Story.

Speaker:              Yael Tauman Kalai, Microsoft Research

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

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

 

 

 

Monday, January 28

 

Seminar on Theoretical Machine Learning

Speaker:              No Seminar

Time/Room:       12:15pm - 1:45pm/No Seminar

 

 

 

 

Tuesday, January 29

 

Computer Science/Discrete Mathematics Seminar II

Topic:                    A Regularity Lemma with Modifications

Speaker:              Guy Moshkovitz, Member, School of Mathematics

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

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

 

1 PCP and Delegating Computation: A Love Story. 
   Yael Tauman Kalai 




In this talk, I will give an overview on how PCPs, combined with
cryptographic tools, are used to generate succinct and efficiently
verifiable proofs for the correctness of computations. I will focus on
constructing (computationally sound) *succinct* proofs that are
*non-interactive* (assuming the existence of public parameters) and are
*publicly verifiable*. In particular, I will focus on a recent result with
Omer Paneth and Lisa Yang, where we show how to construct such proofs for
all polynomial time computations, based on an efficiently falsifiable
decisional assumption on groups with bilinear maps. Prior to this work, this
was only known under non-standard assumptions.

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

2 A Regularity Lemma with Modifications 
   Guy Moshkovitz 




Given an arbitrary graph, we show that if we are allowed to modify (say) 1%
of the edges then it is possible to obtain a much smaller regular partition
than in Szemeredi's original proof of the regularity lemma. Moreover, we
show that it is impossible to improve upon the bound we obtain. 

The upper bound can be used to reprove a famous result of Fox on the removal
lemma [Ann. of Math. '11], whereas the lower bound served as a key step
towards the solution of the optimality question for the hypergraph
regularity lemma. Time permitting, we will give detailed sketches of both
the upper and lower bound proofs. 

Joint work with Asaf Shapira.

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

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/20190128/a3abca5b/attachment.html>