BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//85f20b73fecb3e0e6ca434791a2aea4a.ias.edu//NONSGML kigkonsult.se i
Calcreator 2.29.14//
CALSCALE:GREGORIAN
UID:6a91a074-2231-4b27-b8c5-3038c9974521
X-WR-TIMEZONE:UTC
X-WR-CALNAME:IAS CSDM Seminars
BEGIN:VEVENT
UID:137aac85-2434-4d97-8835-61333fb2b5bd
DTSTAMP:20200401T030216Z
CREATED:20191122T190002Z
DESCRIPTION:Topic: Approximating CSPs on expanding structures\, and applica
tions to codes\n\nSpeaker: Madhur Tulsiani\, Toyota Technological Institut
e at Chicago\n\nVideo: https://video.ias.edu/csdm/2020/0121-MadhurTulsiani
\n\nI will discuss some recent results showing that the sum-of-squares SDP
hierarchy can be used to find approximately optimal solutions to k-CSPs\,
provided that the instance satisfies certain expansion properties. These
properties can be shown to follow from (k-1)-dimensional spectral expansio
n\, but are in fact weaker and also present (for example) in instances whe
re each constraint corresponds to a length-k walk in an expanding graph. I
will also discuss applications to unique and list decoding of direct sum
and direct product codes.\n\nBased on joint works with Vedat Levi Alev\, F
ernando Granha Jeronimo\, Dylan Quintana and Shashank Shrivastava.
DTSTART:20200121T153000Z
DTEND:20200121T173000Z
LAST-MODIFIED:20200226T220428Z
LOCATION:Simonyi Hall 101
SUMMARY:Computer Science/Discrete Mathematics Seminar II
URL:https://www.ias.edu/node/106571
END:VEVENT
BEGIN:VEVENT
UID:20aeb831-0d70-4167-9177-840da29a1cd9
DTSTAMP:20200401T030216Z
CREATED:20190607T202005Z
DESCRIPTION:Topic: Equality Alone Does not Simulate Randomness\n\nSpeaker:
Marc Vinyals\, Technion\n\nVideo: https://video.ias.edu/csdm/2020/0127-Mar
cVinyals\n\nRandomness can provide an exponential saving in the amount of
communication needed to solve a distributed problem\, and the canonical ex
ample of this is the equality function. However\, in many examples where r
andomness helps\, having an efficient way to do hashing would be enough to
solve the problem efficiently. Is hashing all there is to randomness?\n\n
In this talk we show that hashing is not enough. More precisely\, we exhib
it a function that can be solved efficiently using randomized protocols bu
t not if we only allow access to an oracle that computes the equality func
tion\, which models hashing.\n\nJoint work with Arkadev Chattopadhyay and
Shachar Lovett.
DTSTART:20200127T160000Z
DTEND:20200127T170000Z
LAST-MODIFIED:20200226T221027Z
LOCATION:Simonyi Hall 101
SUMMARY:Computer Science/Discrete Mathematics Seminar I
URL:https://www.ias.edu/node/100631
END:VEVENT
BEGIN:VEVENT
UID:3aa313a5-d4d3-444c-9327-9428c5a4dafc
DTSTAMP:20200401T030216Z
CREATED:20190607T203002Z
DESCRIPTION:Topic: Pseudo-deterministic algorithms\n\nSpeaker: Toniann Pita
ssi\, University of Toronto\; Visiting Professor\, School of Mathematics\n
\nA pseudodeterministic algorithm for a search problem (introduced by Gold
wasser and Gat) is a randomized algorithm that must output the *same* corr
ect answer with high probability over all choices of randomness. In this t
alk I will give several motivating examples of search problems that illust
rate the importance of the notion\, and connections with other well-studie
d topics in TCS (i.e.\, explicit constructions of combinatorial objects kn
own to exist by the probabilistic method\, lower bounds for random kSAT\,
inapproximability lower bounds for SOS based algorithms\, and random Resol
ution. After reviewing some known results\, we will prove a Pseudodetermin
istic query lower bound for the (complete) problem of finding a '1' in a v
ector that is promised to have at least a constant fraction of 1's. Our pr
oof uses Huang's Sensitivity Theorem as well as Nullstellensatz/SOS degree
lower bounds and brings up a number of open problems.\nThis work is joint
with Shafi Goldwasser\, Russell Impagliazzo and Rahul Santhanam.
DTSTART:20200128T153000Z
DTEND:20200128T173000Z
LAST-MODIFIED:20200127T143507Z
LOCATION:Simonyi Hall 101
SUMMARY:Computer Science/Discrete Mathematics Seminar II
URL:https://www.ias.edu/node/100731
END:VEVENT
BEGIN:VEVENT
UID:5b82a45a-3c0f-4bdb-8fdd-7b3fa5ac1d4a
DTSTAMP:20200401T030216Z
CREATED:20190607T202005Z
DESCRIPTION:Topic: MIP* = RE \n\nSpeaker: Henry Yuen\, University of Toront
o\n\nVideo: https://video.ias.edu/csdm/2020/0203-HenryYuen\n\nMIP* (pronou
nced “M-I-P star”) denotes the class of problems that admit interactive pr
oofs with quantum entangled provers. It has been an outstanding question t
o characterize the complexity of MIP*. Most notably\, there was no known c
omputable upper bound on MIP*.\n\nWe show that MIP* is equal to the class
RE\, the set of recursively enumerable languages. In particular\, this sho
ws that MIP* contains uncomputable problems. Through a series of known con
nections\, this also yields a negative answer to Connes’ Embedding Problem
from operator algebras. In this talk\, I will explain the connection betw
een Connes' Embedding Problem\, quantum information theory\, and computati
onal complexity. I will then give an overview of our approach\, which invo
lves reducing the Halting Problem to the problem of approximating the enta
ngled value of nonlocal games.\n\nJoint work with Zhengfeng Ji\, Anand Nat
arajan\, Thomas Vidick\, and John Wright.
DTSTART:20200203T160000Z
DTEND:20200203T170000Z
LAST-MODIFIED:20200226T221536Z
LOCATION:Simonyi Hall 101
SUMMARY:Computer Science/Discrete Mathematics Seminar I
URL:https://www.ias.edu/node/100636
END:VEVENT
BEGIN:VEVENT
UID:024154dd-7513-417b-afcc-339eda1b519f
DTSTAMP:20200401T030216Z
CREATED:20190607T203002Z
DESCRIPTION:Topic: Proofs\, Circuits\, Communication\, and Lower Bounds in
Complexity Theory\n\nSpeaker: Robert Robere\, Member\, School of Mathemati
cs\n\nVideo: https://video.ias.edu/csdm/2020/0204-RobertRobere\n\nMany of
the central problems in computational complexity revolve around proving lo
wer bounds on the amount of resources used in various computational models
. In this series of talks\, we will discuss three standard objects in comp
utational complexity --- propositional proofs\, boolean circuits\, and com
munication protocols --- and further describe a three-way connection betwe
en them. Much recent work has profitably exploited this connection (in the
context of so-called ''lifting theorems'') to translate lower bounds from
one model to the other\; we will explore several examples of such theorem
s and suggest some future directions.
DTSTART:20200204T153000Z
DTEND:20200204T173000Z
LAST-MODIFIED:20200226T221708Z
LOCATION:Simonyi Hall 101
SUMMARY:Computer Science/Discrete Mathematics Seminar II
URL:https://www.ias.edu/node/100726
END:VEVENT
BEGIN:VEVENT
UID:ade246ae-2d90-4377-9269-8b41c4e85697
DTSTAMP:20200401T030216Z
CREATED:20200128T143445Z
DESCRIPTION:Topic: Explicit rigid matrices in P^NP via rectangular PCPs\n\n
Speaker: Prahladh Harsha\, Tata Institute of Fundamental Research\n\nVideo
: https://video.ias.edu/csdm/2020/0206-PrahladhHarsha\n\nA nxn matrix M ov
er GF(2) is said to be (r\,\delta)-rigid if every matrix M' within \delta
n^2 Hamming distance from M has rank at least r. A long standing open prob
lem is to construct explicit rigid matrices. In a recent remarkable result
\, Alman and Chen gave explicit constructions of rigid matrices using an N
P oracle. In this talk\, we will give a simplified and improved constructi
on of their result that proves explicit (r\,0.01)-rigid matrices in P^NP w
here 2 = 2^{(log n)^{1-o(1)}}. We obtain our improvement by considering PC
Ps where the query and randomness satisfy a certain 'rectangular property'
.\n\nJoint work with Amey Bhangale\, Orr Paradise and Avishay Tal
DTSTART:20200206T190000Z
DTEND:20200206T200000Z
LAST-MODIFIED:20200226T221754Z
LOCATION:Simonyi 101
SUMMARY:Computer Science/Discrete Mathematics - Special Seminar
URL:https://www.ias.edu/node/108236
END:VEVENT
BEGIN:VEVENT
UID:7a07e67d-1ada-4d4e-933f-1f3e31a58e65
DTSTAMP:20200401T030216Z
CREATED:20190607T202005Z
DESCRIPTION:Topic: Paths and cycles in expanders\n\nSpeaker: Michael Krivel
evich\, Tel Aviv University\n\nVideo: https://video.ias.edu/csdm/2020/0210
-MichaelKrivelevich\n\nExpanders have grown to be one of the most central
and studied notions in modern graph theory. It is thus only natural to res
earch extremal properties of expanding graphs. In this talk we will adapt
the following (rather relaxed) definition of expanders. For a constant alp
ha>0\, a graph G on n vertices is called an alpha-expander if the external
neighborhood of every vertex subset U of size |U|
DTSTART:20200210T160000Z
DTEND:20200210T170000Z
LAST-MODIFIED:20200227T015358Z
LOCATION:Simonyi Hall 101
SUMMARY:Computer Science/Discrete Mathematics Seminar I
URL:https://www.ias.edu/node/100641
END:VEVENT
BEGIN:VEVENT
UID:32fb17ec-f23d-4ced-8a67-e26d13cecccf
DTSTAMP:20200401T030216Z
CREATED:20190607T203002Z
DESCRIPTION:Topic: Proofs\, Circuits\, Communication\, and Lower Bounds in
Complexity Theory\n\nSpeaker: Robert Robere \, Member\, School of Mathemat
ics\n\nVideo: https://video.ias.edu/csdm/2020/0211-RobertRobere\n\nMany of
the central problems in computational complexity revolve around proving l
ower bounds on the amount of resources used in various computational model
s. In this talk we will continue our survey of the connections between thr
ee central models (proofs\, communication\, circuits) from last week\, ske
tching several examples of the so-called 'lifting theorems' for proving lo
wer bounds.
DTSTART:20200211T153000Z
DTEND:20200211T173000Z
LAST-MODIFIED:20200227T015455Z
LOCATION:Simonyi Hall 101
SUMMARY:Computer Science/Discrete Mathematics Seminar II
URL:https://www.ias.edu/node/100721
END:VEVENT
BEGIN:VEVENT
UID:545b3782-f53a-4d4d-b5bc-9c4e8198d5e4
DTSTAMP:20200401T030216Z
CREATED:20190607T203002Z
DESCRIPTION:Topic: An invitation to invariant theory\n\nSpeaker: Viswambhar
a Makam\, Member\, School of Mathematics\n\nVideo: https://video.ias.edu/c
sdm/2020/0217-ViswambharaMakam\n\nThis (mostly expository) talk will be ab
out invariant theory viewed through the lens of computational complexity.
Invariant theory is the study of symmetries\, captured by group actions\,
by polynomials that are “invariant.” Invariant theory has had a deep and l
asting influence in mathematics. In fact\, Lie theory and algebraic geomet
ry\, differential algebra and algebraic combinatorics are all offsprings o
f invariant theory. In our century\, exciting connections between invarian
t theory and fundamental problems in complexity (such as P vs NP) have bee
n uncovered thanks to the Geometric Complexity Theory program.\n\nI will d
iscuss various topics such as degree bounds\, null cones\, orbits and thei
r closures\, and also mention more recent results on non-commutative ident
ity testing. There will be many examples\, and the goal is to familiarize
the audience with the problems\, goals and techniques of interest as well
as the connections with complexity. This talk is intended to provide motiv
ation\, background\, and context for the talk next week. No special backgr
ound will be assumed.
DTSTART:20200218T153000Z
DTEND:20200218T173000Z
LAST-MODIFIED:20200227T015643Z
LOCATION:Simonyi Hall 101
SUMMARY:Computer Science/Discrete Mathematics Seminar II
URL:https://www.ias.edu/node/100716
END:VEVENT
BEGIN:VEVENT
UID:68fff93b-34e4-4fcd-b3dc-3aff8e59a21c
DTSTAMP:20200401T030216Z
CREATED:20190607T202005Z
DESCRIPTION:Topic: Strong Average-Case Circuit Lower Bounds from Non-trivia
l Derandomization\n\nSpeaker: Lijie Chen\, Massachusetts Institute of Tech
nology\n\nVideo: https://video.ias.edu/csdm/2020/0224-LijieChen\n\nWe prov
e that\, unconditionally\, for all constants a\, NQP = NTIME[n^polylog(n)]
cannot be (1/2 + 2^(-log^a n) )-approximated by 2^(log^a n)-size ACC^0 ci
rcuits. Previously\, it was even open whether E^NP can be (1/2+1/sqrt(n))-
approximated by AC^0[2] circuits. As a straightforward application\, we ob
tain an infinitely often non-deterministic pseudorandom generator for poly
-size ACC^0 circuits with seed length 2^{log^eps n}\, for all eps > 0.\n\n
More generally\, we establish a connection showing that\, for a typical ci
rcuit class C\, non-trivial nondeterministic algorithms estimating the acc
eptance probability of a given S-size C circuit with an additive error 1/S
imply strong (1/2 + 1/n^{omega(1)}) average-case lower bounds for nondete
rministic time classes against C circuits. The existence of such (determin
istic) algorithms is much weaker than the widely believed conjecture Promi
seBPP = PromiseP.\n\nOur new results build on a line of recent works\, inc
luding [Murray and Williams\, STOC 2018]\, [Chen and Williams\, CCC 2019]\
, and [Chen\, FOCS 2019]. In particular\, it strengthens the corresponding
(1/2 + 1/polylog(n))-inapproximability average-case lower bounds in [Chen
\, FOCS 2019]. The two important technical ingredients are techniques from
Cryptography in NC^0 [Applebaum et al.\, SICOMP 2006]\, and Probabilistic
Checkable Proofs of Proximity with NC^1-computable proofs.\n\nThis is joi
nt work with Hanlin Ren from Tsinghua University.
DTSTART:20200224T160000Z
DTEND:20200224T170000Z
LAST-MODIFIED:20200227T015752Z
LOCATION:Simonyi Hall 101
SUMMARY:Computer Science/Discrete Mathematics Seminar I
URL:https://www.ias.edu/node/100646
END:VEVENT
BEGIN:VEVENT
UID:72a99409-15ee-4b44-919a-c95d369ddf96
DTSTAMP:20200401T030216Z
CREATED:20190607T203002Z
DESCRIPTION:Topic: Is the variety of singular tuples of matrices a null con
e?\n\nSpeaker: Viswambhara Makam\, Member\, School of Mathematics\n\nVideo
: https://video.ias.edu/csdm/2020/0225-ViswambharaMakam\n\nThe following m
ulti-determinantal algebraic variety plays an important role in algebra an
d computational complexity theory: SING_{n\,m}\, consisting of all m-tuple
s of n x n complex matrices which span only singular matrices. In particul
ar\, an efficient deterministic algorithm testing membership in SING_{n\,m
} will imply super-polynomial circuit lower bounds\, a holy grail of the t
heory of computation.\n\nA sequence of recent works suggests such efficien
t algorithms for memberships in a general class of algebraic varieties\, n
amely the null cones of linear group actions. Can this be used for the pro
blem above? To address this we will use ideas and techniques from various
algebraic\, geometric\, and combinatorial fields. As always\, no backgroun
d will be assumed.\n\nThis is joint work with Avi Wigderson.
DTSTART:20200225T153000Z
DTEND:20200225T173000Z
LAST-MODIFIED:20200227T022052Z
LOCATION:Simonyi Hall 101
SUMMARY:Computer Science/Discrete Mathematics Seminar II
URL:https://www.ias.edu/node/100711
END:VEVENT
BEGIN:VEVENT
UID:462d7a29-71e0-4cbd-98d0-09e8cd9eb3b0
DTSTAMP:20200401T030216Z
CREATED:20200226T162657Z
DESCRIPTION:Topic: Spectral Independence in High-dimensional Expanders and
Applications to the Hardcore Model\n\nSpeaker: Kuikui Liu\, University of
Washington\n\nVideo: https://video.ias.edu/csdm/2020/0227-KuikuiLiu\n\nWe
say a probability distribution µ is spectrally independent if an associate
d correlation matrix has a bounded largest eigenvalue for the distribution
and all of its conditional distributions. We prove that if µ is spectrall
y independent\, then the corresponding high dimensional simplicial complex
is a local spectral expander. Using a line of recent works on mixing time
of high dimensional walks on simplicial complexes [KM17\; DK17\; KO18\; A
L19]\, this implies that the corresponding Glauber dynamics mixes rapidly
and generates (approximate) samples from µ. As an application\, we show th
at natural Glauber dynamics mixes rapidly (in polynomial time) to generate
a random independent set from the hardcore model up to the uniqueness thr
eshold. This improves the quasi-polynomial running time of Weitz’s determi
nistic correlation decay algorithm [Wei06] for estimating the hardcore par
tition function\, also answering a long-standing open problem of mixing ti
me of Glauber dynamics [LV97\; LV99\; DG00\; Vig01\; Eft+16].\n\nJoint wor
k with Nima Anari and Shayan Oveis Gharan
DTSTART:20200227T193000Z
DTEND:20200227T203000Z
LAST-MODIFIED:20200228T191311Z
LOCATION:Simonyi Hall 101
SUMMARY:Computer Science/Discrete Mathematics Seminar II
URL:https://www.ias.edu/node/109666
END:VEVENT
BEGIN:VEVENT
UID:ec7fcb66-f9b1-4403-a253-3f71e2ba3686
DTSTAMP:20200401T030216Z
CREATED:20190607T202005Z
DESCRIPTION:Topic: An Improved Cutting Plane Method for Convex Optimization
\, Convex-Concave Games and its Applications\n\nSpeaker: Zhao Song\, Membe
r\, School of Mathematics\n\nVideo: https://video.ias.edu/csdm/2020/0302-Z
haoSong\n\nGiven a separation oracle for a convex set $K \subset \mathbb{R
}^n$ that is contained in a box of radius $R$\, the goal is to either comp
ute a point in $K$ or prove that $K$ does not contain a ball of radius $\e
psilon$. We propose a new cutting plane algorithm that uses an optimal $O(
n \log (\kappa))$ evaluations of the oracle and an additional $O(n^2)$ tim
e per evaluation\, where $\kappa = nR/\epsilon$.\n\n- This improves upon V
aidya's $O( \text{SO} \cdot n \log (\kappa) + n^{\omega+1} \log (\kappa))$
time algorithm [Vaidya\, FOCS 1989a] in terms of polynomial dependence on
$n$\, where $\omega\n- This improves upon Lee-Sidford-Wong's $O( \text{SO
} \cdot n \log (\kappa) + n^3 \log^{O(1)} (\kappa))$ time algorithm [Lee\,
Sidford and Wong\, FOCS 2015] in terms of dependence on $\kappa$.\n\nFor
many important applications in economics\, $\kappa = \Omega(\exp(n))$ and
this leads to a significant difference between $\log(\kappa)$ and poly$(\l
og (\kappa))$. We also provide evidence that the $n^2$ time per evaluation
cannot be improved and thus our running time is optimal.A bottleneck of p
revious cutting plane methods is to compute leverage scores\, a measure of
the relative importance of past constraints.Our result is achieved by a n
ovel multi-layered data structure for leverage score maintenance\, which i
s a sophisticated combination of diverse techniques such as random project
ion\, batched low-rank update\, inverse maintenance\, polynomial interpola
tion\, and fast rectangular matrix multiplication. Interestingly\, our met
hod requires a combination of different fast rectangular matrix multiplica
tion algorithms. Our algorithm not only works for the classical convex opt
imization setting\, but also generalizes to convex-concave games. We apply
our algorithm to improve the runtimes of many interesting problems\, e.g.
\, Linear Arrow-Debreu Markets\, Fisher Markets\, and Walrasian equilibriu
m.\n\nThis is a joint work with Haotian Jiang\, Yin Tat Lee\, and Sam Chiu
-wai Wong
DTSTART:20200302T160000Z
DTEND:20200302T170000Z
LAST-MODIFIED:20200401T000928Z
LOCATION:Simonyi Hall 101
SUMMARY:Computer Science/Discrete Mathematics Seminar I
URL:https://www.ias.edu/node/100651
END:VEVENT
BEGIN:VEVENT
UID:d802156e-070c-4f1d-bc39-bfe818eaf6f2
DTSTAMP:20200401T030216Z
CREATED:20190607T203002Z
DESCRIPTION:Topic: An introduction to Boolean Function Analysis\n\nSpeaker:
Dor Minzer\, Member\, School of Mathematics\n\nVideo: https://video.ias.e
du/csdm/2020/0303-DorMinzer\n\nWe will discuss some of the basic principle
s and results in the study of Boolean-valued functions over the discrete h
ypercube using discrete Fourier analysis. In particular\, we will talk abo
ut basic concepts\, the hypercontractive inequality and the KKL theorem. T
ime permitting\, we will discuss the Fourier-Entropy Conjecture and mentio
n some recent progress towards it.\n\nThe talk is self-contained and no sp
ecial background will be assumed.
DTSTART:20200303T153000Z
DTEND:20200303T173000Z
LAST-MODIFIED:20200401T001126Z
LOCATION:Simonyi Hall 101
SUMMARY:Computer Science/Discrete Mathematics Seminar II
URL:https://www.ias.edu/node/100706
END:VEVENT
BEGIN:VEVENT
UID:55bffb30-7578-4679-8b5a-1a60f4cf6c71
DTSTAMP:20200401T030216Z
CREATED:20190607T202005Z
DESCRIPTION:Topic: Learning from Censored and Dependent Data\n\nSpeaker: Co
nstantinos Daskalakis \, Massachusetts Institute of Technology\; Member\,
School of Mathematics\n\nVideo: https://video.ias.edu/csdm/2020/0309-Const
antinosDaskalakis\n\nMachine Learning is invaluable for extracting insight
s from large volumes of data. A key assumption enabling many methods\, how
ever\, is having access to training data comprising independent observatio
ns from the entire distribution of relevant data. In practice\, data is co
mmonly missing due to measurement limitations\, legal restrictions\, or da
ta collection and sharing practices. Moreover\, observations are commonly
collected on a network\, a spatial or a temporal domain and may be intrica
tely dependent. Training on data that is censored or dependent is known to
lead to Machine Learning models that are biased.\n\nIn this talk\, we ove
rview recent work on learning from censored and dependent data. We propose
a learning framework which is broadly applicable\, and instantiate this f
ramework to obtain computationally and statistically efficient methods for
linear\, and logistic regression from censored or dependent samples\, in
high dimensions. Our findings are enabled through connections to Statistic
al Physics\, Concentration and Anti-concentration of measure\, and propert
ies of Stochastic Gradient Descent\, and advance some classical challenges
in Statistics and Econometrics. (I will overview works with Dagan\, Dikka
la\, Gouleakis\, Ilyas\, Jayanti\, Kontonis\, Panageas\, Rohatgi\, Tzamos\
, Zampetakis)
DTSTART:20200309T150000Z
DTEND:20200309T160000Z
LAST-MODIFIED:20200401T001326Z
LOCATION:Simonyi Hall 101
SUMMARY:Computer Science/Discrete Mathematics Seminar I
URL:https://www.ias.edu/node/100656
END:VEVENT
BEGIN:VEVENT
UID:f7e38a88-922f-4744-8564-44b85eb429d7
DTSTAMP:20200401T030216Z
CREATED:20190607T203002Z
DESCRIPTION:Topic: Introduction to high dimensional expanders \n\nSpeaker:
Irit Dinur\, Weizmann Institute of Science\; Visiting Professor\, School o
f Mathematics\n\nVideo: https://video.ias.edu/csdm/2020/0310-IritDinur\n\n
High dimensional expansion generalizes edge and spectral expansion in grap
hs to hypergraphs (viewed as higher dimensional simplicial complexes). It
is a tool that allows analysis of PCP agreement rests\, mixing of Markov c
hains\, and construction of new error correcting codes. My talk will be de
voted to proving some nice relations between local and global expansion of
these objects.
DTSTART:20200310T143000Z
DTEND:20200310T163000Z
LAST-MODIFIED:20200401T001557Z
LOCATION:Simonyi Hall 101
SUMMARY:Computer Science/Discrete Mathematics Seminar II
URL:https://www.ias.edu/node/100701
END:VEVENT
BEGIN:VEVENT
UID:a2381f34-d5c8-4bed-8fd0-8e29dc44f96f
DTSTAMP:20200401T030216Z
CREATED:20200313T194133Z
DESCRIPTION:Topic: Feature purification: How adversarial training can perfo
rm robust deep learning\n\nSpeaker: Yuanzhi Li\, Carnegie Mellon Universit
y\n\nVideo: https://video.ias.edu/csdm/2020/0316-YuanzhiLi\n\nTo connect t
o the CSDM Seminar via Zoom\, please do the following:\n1 - If you have Zo
om installed on your device\, enter the following meeting ID: 360043913 \,
click Join Meeting.\n2 - If you do not have Zoom installed\, click the fo
llowing link to download and install: https://theias.zoom.us/j/360043913\n
3 - Once installed\, click the very same link to connect to the meeting.\n
\nWhy deep learning models\, trained on many machine learning tasks\, can
obtain nearly perfect predictions of unseen data sampled from the same dis
tribution but are extremely vulnerable to small perturbations of the input
? How can adversarial training improve the robustness of the neural networ
ks over such perturbations? In this work\, we developed a new principle ca
lled 'feature purification''. Mathematically\, the principle states that f
or a multi-layer ReLU neural network\, let w_i^0 be the weight of the i-th
neuron at initialization\, w_i be its weight after clean training (starti
ng from w_i^0)\, and w_i' as its weight after adversarial training (starti
ng from w_i)\, then for most of the neurons\, there are scaling factors \b
eta_i and vectors v_i such that w_i = \beta_i w_i' + v_i with ||\beta_i w_
i' || > ||v_i||\, while both w_i and w_i' have nearly zero correlations wi
th w_i^0.\n\nConceptually\, the principle says that while both clean train
ing and adversarial training will discover certain features fundamentally
different from the initial values\, clean training actually already discov
ers a big portion of the 'robust features' obtained by adversarial trainin
g. Thus\, instead of needing to learn new 'robust features' or completely
remove 'non-robust features'\, adversarial training can simply robustify t
he neural network by purifying the clean trained features.\n\nIn this work
\, we present both experiments demonstrating the principle\, and a mathema
tical model formally proving it. In particular\, we show that for certain
binary classification tasks\, when we train a two-layer ReLU network using
SGD\, (1). Both clean training and adversarial training will learn featur
es with nearly zero correlations with the (random) initialization. (2). Af
ter clean training\, the network will provably achieve > 99% clean accurac
y but 99% robust accuracy in polynomial samples and running time by simply
'purifying' the clean trained features. Our lower bound that clean traine
d network has\n\nOur work also sheds light on why 'adversary examples are
not bugs': They are not because neural networks are over-fitting to the da
ta set due to the high complexity of the models with insufficiently many t
raining data\, but rather are an intrinsic property of the gradient-descen
t type training algorithms.
DTSTART:20200316T150000Z
DTEND:20200316T160000Z
LAST-MODIFIED:20200401T001742Z
LOCATION:https://theias.zoom.us/j/360043913
SUMMARY:Computer Science/Discrete Mathematics Seminar I
URL:https://www.ias.edu/node/110126
END:VEVENT
BEGIN:VEVENT
UID:90ac3328-a5dd-4f1d-b9fd-ffc4f025b733
DTSTAMP:20200401T030216Z
CREATED:20190607T203002Z
DESCRIPTION:Topic: Sharp Thresholds and Extremal Combinatorics\n\nSpeaker:
Dor Minzer\, Member\, Institute for Advanced Study\n\nVideo: https://video
.ias.edu/csdm/2020/0317-DorMinzer\n\nTo connect to the CSDM Seminar via Zo
om\, please do the following:\n1 - If you have Zoom installed on your devi
ce\, enter the following meeting ID: 360043913 \, click Join Meeting.\n2 -
If you do not have Zoom installed\, click the following link to download
and install: https://theias.zoom.us/j/360043913\n3 - Once installed\, clic
k the very same link to connect to the meeting.\n\nConsider the p-biased d
istribution over ${0\,1}^n$\, in which each coordinate independently is sa
mpled according to a $p$-biased bit. A sharp-threshold result studies the
behavior of Boolean functions over the hypercube under different p-biased
measures\, and in particular whether the function experiences a phase tran
sition between two\, close p's. While the theory of sharp-thresholds is we
ll understood for p's that are bounded away from 0 and 1\, it is much less
so for values of p that are close to 0 or 1.\n\nIn this talk\, we will fi
rst discuss classical sharp-threshold results\, and demonstrate an applica
tion of them in Extremal Combinatorics [Dinur-Friedgut]. We will then disc
uss newer sharp-threshold results. Time permitting\, we will mention appli
cations to two problems in extremal combinatorics: the Erdos matching conj
ecture\, and the problem of determining the largest family of vectors in [
m]^n that avoids a fixed\, constant-sized intersections.\n\nBased on joint
works with Peter Keevash\, Noam Lifshitz and Eoin Long.
DTSTART:20200317T143000Z
DTEND:20200317T163000Z
LAST-MODIFIED:20200401T001815Z
LOCATION:https://theias.zoom.us/j/360043913
SUMMARY:Computer Science/Discrete Mathematics Seminar II
URL:https://www.ias.edu/node/100696
END:VEVENT
BEGIN:VEVENT
UID:47e15697-af8f-40ff-8a85-1fadb0b36c27
DTSTAMP:20200401T030216Z
CREATED:20190607T202005Z
DESCRIPTION:Topic: Optimal tiling the Euclidean space using symmetric bodie
s\n\nSpeaker: Mark Braverman\, Princeton University\n\nWe say a body B til
es the space R^n if the shifted bodies (B+z)\, for z\in Z^n\, are all disj
oint and cover R^n.\n\nIn this talk\, we consider the problem of finding t
he least surface area a tiling body B can have\, for bodies B symmetric un
der coordinate permutation. This problem arises naturally in the study of
parallel repetition theorems\, which are an important component in many ha
rdness of approximation results. For general bodies\, the isoperimeric ine
quality implies that any tiling body B must have surface area at least \sq
rt{n}\, and somewhat surprisingly this bound is asymptotically tight.\n\nW
ith the symmetry requirement\, the trivial upper bound is O(n) for the uni
t cube\, and the trivial lower bound is still \sqrt{n}. In this talk we sh
ow that the answer for the symmetric case is \Theta(n/\sqrt{\log n}).\n\nW
e will discuss connections to the parallel repetition theorem. Specificall
y\, while the strong parallel repetition conjecture was refuted by Raz in
2008\, our result suggests that there might be important special cases whe
re it still applies.\n\nJoint work with Dor Minzer
DTSTART:20200323T150000Z
DTEND:20200323T160000Z
LAST-MODIFIED:20200323T105516Z
LOCATION:https://theias.zoom.us/j/360043913
SUMMARY:Computer Science/Discrete Mathematics Seminar I
URL:https://www.ias.edu/node/100666
END:VEVENT
BEGIN:VEVENT
UID:a24c78dc-557c-4b7b-b5d3-c0315ef4c408
DTSTAMP:20200401T030216Z
CREATED:20190607T203002Z
DESCRIPTION:Topic: High dimensional expansion and agreement testing\n\nSpea
ker: Irit Dinur\, Weizmann Institute of Science\; Visiting Professor\, Sch
ool of Mathematics\n\nVideo: https://video.ias.edu/csdm/2020/0324-IritDinu
r\n\nIn this talk I will describe the notion of 'agreement tests' that are
motivated by PCPs but stand alone as a combinatorial property-testing que
stion. I will show that high dimensional expanders support agreement tests
\, thereby derandomizing direct product tests in a very strong way.
DTSTART:20200324T143000Z
DTEND:20200324T163000Z
LAST-MODIFIED:20200401T001920Z
LOCATION:https://theias.zoom.us/j/360043913
SUMMARY:Computer Science/Discrete Mathematics Seminar II
URL:https://www.ias.edu/node/100691
END:VEVENT
BEGIN:VEVENT
UID:7c932ad6-9d3a-42ce-90bb-d362e7b61006
DTSTAMP:20200401T030216Z
CREATED:20190607T202005Z
DESCRIPTION:Topic: CSPs with Global Modular Constraints: Algorithms and Har
dness via Polynomial Representations\n\nSpeaker: Sivakanth Gopi\n\nVideo:
https://video.ias.edu/csdm/2020/0330-SivakanthGopi\n\nA theorist's dream i
s to show that hard instances/obstructions for an (optimal) algorithm can
be used as gadgets to prove tight hardness reductions (which proves optima
lity of the algorithm). An example of such a result is that of Prasad Ragh
avendra who showed that for any constraint satisfaction problem (CSP)\, th
ere is an SDP which achieves the best possible approximation factor assumi
ng UGC. We show that a similar phenomenon occurs in CSPs with global modul
ar constraints.\n\nA global modular constraint is a linear equation (in al
l the variables) modulo M for some fixed constant M. Take any polytime sol
vable Boolean CSP like 2SAT or LIN_2 or HORNSAT. Let's look at LIN_2 for c
oncreteness\, it is a system of linear equations modulo 2. By Gaussian eli
mination over F_2\, we can find in polynomial time if it is satisfiable. N
ow suppose we are given an additional linear equation modulo M (for some f
ixed constant M not equal to 2). Can we find in polynomial time if the new
system is satisfiable? Surprisingly\, we show that the answer depends on
the prime factorization of M! For example\, it is possible for M=3\, but n
ot for M=15. We show that for such problems\, the obstructions to a natura
l algorithm and gadgets useful for hardness reduction (assuming ETH) are c
losely connected to complexity (like degree or sparsity) of polynomial rep
resentations of OR mod M. Thus showing good lower bounds on the complexity
of such polynomials imply good algorithms and constructing low complexity
representations imply good hardness results. We also show some connection
s to submodular minimization with global modular constraints.\n\nJoint wor
k with Joshua Brakensiek and Venkatesan Guruswami.
DTSTART:20200330T150000Z
DTEND:20200330T160000Z
LAST-MODIFIED:20200401T002203Z
LOCATION:https://theias.zoom.us/j/360043913
SUMMARY:Computer Science/Discrete Mathematics Seminar I
URL:https://www.ias.edu/node/100671
END:VEVENT
BEGIN:VEVENT
UID:6489e07a-e241-471b-9645-e1cb84d0be04
DTSTAMP:20200401T030216Z
CREATED:20190607T203002Z
DESCRIPTION:Topic: High dimensional expansion and agreement testing\n\nSpea
ker: Irit Dinur\, Weizmann Institute of Science\; Visiting Professor\, Sch
ool of Mathematics\n\nVideo: https://video.ias.edu/csdm/2020/0331-IritDinu
r\n\nIn this talk I will describe the notion of 'agreement tests' that are
motivated by PCPs but stand alone as a combinatorial property-testing que
stion. I will show that high dimensional expanders support agreement tests
\, thereby derandomizing direct product tests in a very strong way.
DTSTART:20200331T143000Z
DTEND:20200331T163000Z
LAST-MODIFIED:20200401T002303Z
LOCATION:https://theias.zoom.us/j/360043913
SUMMARY:Computer Science/Discrete Mathematics Seminar II
URL:https://www.ias.edu/node/100686
END:VEVENT
BEGIN:VEVENT
UID:e9ad43de-537d-40c6-affc-d4f73b3da428
DTSTAMP:20200401T030216Z
CREATED:20190607T203002Z
DESCRIPTION:Topic: To Be Announced\n\nSpeaker: To Be Announced\n\n
DTSTART:20200407T143000Z
DTEND:20200407T163000Z
LAST-MODIFIED:20200331T174735Z
LOCATION:
SUMMARY:Computer Science/Discrete Mathematics Seminar II
URL:https://www.ias.edu/node/100681
END:VEVENT
BEGIN:VEVENT
UID:d54331a5-7fda-43fe-9227-ef46eb673fb3
DTSTAMP:20200401T030216Z
CREATED:20200219T150300Z
DESCRIPTION:Topic: To Be Announced\n\nSpeaker: Kobbi Nissim \, Georgetown U
niversity\n\n
DTSTART:20200427T150000Z
DTEND:20200427T160000Z
LAST-MODIFIED:20200331T174700Z
LOCATION:
SUMMARY:Computer Science/Discrete Mathematics Seminar I
URL:https://www.ias.edu/node/109426
END:VEVENT
BEGIN:VEVENT
UID:6ab448fd-f35d-4274-969a-b990390b19ee
DTSTAMP:20200401T030216Z
CREATED:20200124T160538Z
DESCRIPTION:Topic: Using discrepancy theory to improve the design of random
ized controlled trials\n\nSpeaker: Dan Spielman\, Yale University\n\n
DTSTART:20200511T150000Z
DTEND:20200511T160000Z
LAST-MODIFIED:20200331T174534Z
LOCATION:
SUMMARY:Computer Science/Discrete Mathematics Seminar I
URL:https://www.ias.edu/node/108111
END:VEVENT
END:VCALENDAR