BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//85f20b73fecb3e0e6ca434791a2aea4a.ias.edu//NONSGML kigkonsult.se i
Calcreator 2.41.43//
CALSCALE:GREGORIAN
UID:33633435-3339-4635-b565-623232376338
X-WR-TIMEZONE:UTC
X-WR-CALNAME:IAS CSDM Seminars
BEGIN:VEVENT
UID:36643464-3733-4238-b130-633934323230
DTSTAMP:20220518T201702Z
CREATED:20211027T173941Z
DESCRIPTION:Topic: PAC Learnability of partial concept classes\n\nSpeakers:
Noga Alon\n\nAffiliation: Princeton University\n\nWe extend the classical
theory of PAC learning in a way which allows\nto model a rich variety of
practical learning tasks where the data\nsatisfies special properties that
ease the learning process. This is\ndone by considering partial concepts:
functions that can be undefined\non certain parts of the space\, providin
g a natural way to express\nassumptions on the data such as satisfying mar
gin conditions.\n\nWe characterize PAC learnability of partial concept cla
sses and reveal\nan algorithmic landscape which is fundamentally different
than the\nclassical one. We also show that there are easy-to-learn partia
l\nconcept classes which probably cannot be captured by the traditional\nP
AC theory\, resolving in a strong sense a recent problem of Attias\,\nKont
orovich and Mansour.\n\nJoint work with Steve Hanneke\, Ron Holzman and Sh
ay Moran.
DTSTART:20220221T161500Z
DTEND:20220221T171500Z
LAST-MODIFIED:20220203T174702Z
LOCATION:Simonyi 101 and Remote Access
SUMMARY:Computer Science/Discrete Mathematics Seminar I
URL:https://www.ias.edu/math/events/computer-sciencediscrete-mathematics-se
minar-i-501
END:VEVENT
BEGIN:VEVENT
UID:64646438-6262-4262-a266-633136626431
DTSTAMP:20220518T201702Z
CREATED:20211210T162249Z
DESCRIPTION:Topic: Derandomization and its connections throughout complexit
y theory\n\nSpeakers: Liije Chen\n\nAffiliation: Massachusetts Institute o
f Technology\n\nThis is the second talk in a three-part series presented t
ogether with\nRoei Tell.\n\nThe series is intended to survey the fast-pace
d recent developments in\nthe study of derandomization. We will present:\n
\n * A revised version of the classical hardness vs randomness\nframework\
, converting new types of uniform lower bounds into\nnon-black-box derando
mization algorithms.\n * Unconditional derandomization of an important cla
ss of\nMerlin-Arthur protocols\, and stronger circuit lower bounds from\nd
erandomization.\n * Optimal derandomization algorithms that incur essentia
lly no\nruntime overhead (a.k.a 'free lunch derandomization').\n\nThe seco
nd talk will present the recent developments on proving\ncircuit lower bou
nds from non-trivial derandomization (a.k.a.\, the\nalgorithmic method).
As the main focus\, I will show how to\nderandomize Merlin-Arthur protocol
s with ACC^0 verifiers in\nnondeterministic quasi-polynomial time infinite
ly often and\nconsequently deduce ACC^0 lower bounds.\n\nI will first pres
ent a recent perspective on the algorithmic method\nthat decomposes the wh
ole proof into three conceptual ingredients and\nshow how these three ingr
edients lead to new circuit lower bounds. \nNext\, I will explain one of t
he ingredients in more detail: an\napproach for unconditionally derandomiz
ing Merlin-Arthur protocols\nwhose verifiers have small circuits from a ce
rtain circuit class.
DTSTART:20220222T153000Z
DTEND:20220222T173000Z
LAST-MODIFIED:20220222T133410Z
LOCATION:Simonyi Hall 101 and Remote Access
SUMMARY:Computer Science/Discrete Mathematics Seminar II
URL:https://www.ias.edu/math/events/computer-sciencediscrete-mathematics-se
minar-ii-499
END:VEVENT
BEGIN:VEVENT
UID:64653834-3336-4137-a436-346132643731
DTSTAMP:20220518T201702Z
CREATED:20211027T174359Z
DESCRIPTION:Topic: Refuting Smoothed k-SAT Formulas and a Proof of Feige's
Conjecture\n\nSpeakers: Pravesh Kothari\n\nAffiliation: Carnegie Mellon Un
iversity\n\nI'll present a new algorithm to refute\, that is\, efficiently
find\ncertificates of unsatisfiability\, for smoothed instances of k-SAT
and\nother CSPs. Smoothed instances are produced by starting with a\nworst
-case instance and flipping each literal in every clause\nindependently wi
th a small constant probability. The 'clause'\nstructure in such instances
is arbitrary and the only randomness is in\nthe literal patterns. The tra
de-off between the density\, i.e.\, the\nnumber of constraints in the inst
ance and the running time required by\nthe algorithm matches (up to polylo
garithmic factors density) the best\nknown (and possibly sharp) trade-off
for random k-SAT. As a corollary\,\nwe also obtain a simpler analysis for
refuting random k-SAT formulas.\n\nOur analysis inspires a new method that
we use to prove Feige's 2008\nconjecture on the trade-off between the siz
e of the hypergraph and its\ngirth that generalizes the Moore bound on the
girth of irregular\ngraphs proved by Alon\, Hoory\, and Linial (2002). As
a corollary\, we\nobtain that smoothed instances of 3-sat with arbitrary
clause\nstructure and ~n^{1.4} (<< n^{1.5}\, the threshold for known effic
ient\nrefutation) constraints admit polynomial-size certificates of\nunsat
isfiability with appropriate generalization to all k-CSPs. This\nextends t
he celebrated work of Feige\, Kim\, and Ofek (2006) who proved\na similar
result for random 3-sat. FKO's proof uses a\n2nd-moment-method based argum
ent that strongly exploits the randomness\nof the clause structure. Our pr
oof gives a simpler argument that\nextends to ``worst-case' clause structu
res. \n\nTaken together\, our results show that smoothed instances with\na
rbitrary clause structure and considerably less randomness enjoy the\nsame
thresholds for both refutation algorithms and certificates of\nunsatisfia
bility as random instances.\n\nBased on joint work with Venkat Guruswami (
CMU/Berkeley) and Peter\nManohar (CMU).
DTSTART:20220228T161500Z
DTEND:20220228T171500Z
LAST-MODIFIED:20220228T160251Z
LOCATION:Simonyi 101 and Remote Access
SUMMARY:Computer Science/Discrete Mathematics Seminar I
URL:https://www.ias.edu/math/events/computer-sciencediscrete-mathematics-se
minar-i-502
END:VEVENT
BEGIN:VEVENT
UID:39323436-3937-4331-b239-343562396630
DTSTAMP:20220518T201702Z
CREATED:20211210T162304Z
DESCRIPTION:Topic: Non-Black-Box Derandomization\n\nSpeakers: Roei Tell\n\n
Affiliation: Member\, School of Mathematics\n\nThis is the third and final
talk in the joint series with Lijie Chen\n[https://www.mit.edu/~lijieche/
]. The talk will NOT rely on the\ntechnical contents from the two previous
talks.\n\nI will present a joint work with Lijie\n[https://eccc.weizmann.
ac.il/report/2021/080/]\, in which we revise the\nhardness vs randomness f
ramework so that it can work in a\nnon-black-box fashion. That is\, we con
struct derandomization\nalgorithms that do not rely on classical PRGs\, an
d instead 'extract\npseudorandomness' from the given input on which we wan
t to simulate\nthe probabilistic machine.\n\nUsing a non-black-box approac
h allows us to deduce stronger\nconclusions (or alternatively rely on weak
er hypotheses)\, compared to\nclassical approaches. In particular\, I will
present two such results:\n\n1. 'Free lunch' derandomization\, in which w
e eliminate randomness at\nessentially no observable cost in the running t
ime.\n\n2. A new approach to the prBPP = prP conjecture\, which connects t
he\nconjecture to a specific type of uniform lower bounds that we\nintrodu
ce.
DTSTART:20220301T153000Z
DTEND:20220301T173000Z
LAST-MODIFIED:20220301T141401Z
LOCATION:Simonyi Hall 101 and Remote Access
SUMMARY:Computer Science/Discrete Mathematics Seminar II
URL:https://www.ias.edu/math/events/computer-sciencediscrete-mathematics-se
minar-ii-500
END:VEVENT
BEGIN:VEVENT
UID:64643763-3462-4136-a535-633862323239
DTSTAMP:20220518T201702Z
CREATED:20211027T174555Z
DESCRIPTION:Topic: The Minimum Formula Size Problem is (ETH) Hard\n\nSpeake
rs: Rahul Ilango\n\nAffiliation: Massachusetts Institute of Technology\n\n
Understanding the complexity of the Minimum Circuit Size Problem\n(MCSP) i
s a longstanding mystery in theoretical computer science.\nDespite being a
natural problem about circuits (given a Boolean\nfunction's truth table\,
determine the size of the smallest circuit\ncomputing it)\, answers to ba
sic questions about MCSP still elude us\n(for example\, is it NP-hard?). T
his mystery is compounded by recent\nwork showing intriguing connections b
etween basic questions about MCSP\nand open problems in a growing number o
f areas\, including\ncryptography\, average-case complexity\, and learning
theory.\n\nIn this talk\, I will review this background and motivation (n
o prior\nknowledge on MCSP required) and then discuss work that builds tow
ards\nbasing the intractability of MCSP on standard worst-case assumptions
.\nMore specifically\, in the latter part I will talk about how one can\ns
how the 'formula version' of MCSP (the Minimum _Formula_ Size\nProblem) is
not in P if the Exponential Time Hypothesis holds.
DTSTART:20220307T161500Z
DTEND:20220307T171500Z
LAST-MODIFIED:20220307T115617Z
LOCATION:Simonyi 101 and Remote Access
SUMMARY:Computer Science/Discrete Mathematics Seminar I
URL:https://www.ias.edu/math/events/computer-sciencediscrete-mathematics-se
minar-i-503
END:VEVENT
BEGIN:VEVENT
UID:31376334-6237-4361-a166-303236633130
DTSTAMP:20220518T201702Z
CREATED:20211210T162317Z
DESCRIPTION:Topic: Hardness of Easy Problems and Fine-Grained Complexity\n
\nSpeakers: Or Zamir\n\nAffiliation: Member\, School of Mathematics\n\nIn
recent years\, a new “fine-grained” theory of computational\nhardness has
been developed\, based on “fine-grained reductions”\nthat focus on exact r
unning times for problems. \n\nWe follow the fashion of NP-hardness in a m
ore delicate manner. We\nidentify key problems for which we have a time t(
n) solution\, but\nbelieve that there is no $t(n)^{(1-eps)}$ solution for
any eps>0.\nThen\, we reduce the key problems in a fine-grained way to man
y\nimportant problems. Thus\, getting a tight conditional lower-bounds for
\nthem.\n\nThis approach has led to the discovery of many meaningful\nrela
tionships between problems\, and to equivalence classes. One such\nkey con
jecture is a quantitative strengthening of the P!=NP conjecture\ncalled SE
TH. \n\nResearch on SETH-based lower bounds has flourished in particular
in\nrecent years. Showing\, for example\, that the classical algorithms ar
e\nlikely optimal for problems such as Diameter\, Sub-tree Isomorphism\,\n
Edit Distance and Longest Common Subsequence. \n\nIn the first half of the
seminar we will introduce and survey the\nclassic conjectures and tools o
f these fine-grained reductions.\n\nIn the second half of it we will cover
a recent technique (joint work\nwith Abboud\, Bringmann and Khoury) that
translates many of these\nconditional-lower bounds to hold also for approx
imation algorithms.\nFor example\, we show that no distance oracle with O(
1)-approximation\,\n$m^{(1+o(1))}$ preprocessing time and $m^{o(1)}$ query
time is likely\nto exist.
DTSTART:20220308T153000Z
DTEND:20220308T173000Z
LAST-MODIFIED:20220308T133112Z
LOCATION:Simonyi Hall 101 and Remote Access
SUMMARY:Computer Science/Discrete Mathematics Seminar II
URL:https://www.ias.edu/math/events/computer-sciencediscrete-mathematics-se
minar-ii-501
END:VEVENT
BEGIN:VEVENT
UID:38353637-3438-4561-b062-376462386536
DTSTAMP:20220518T201702Z
CREATED:20211027T174758Z
DESCRIPTION:Topic: Multi-group learning via Outcome Indistinguishability\n
\nSpeakers: Gal Yona\n\nAffiliation: Weizmann Institute\n\nAs machine lear
ning is widely deployed\, it is increasingly important\nto ensure that pre
dictors will perform well not only on\naverage (across the entire populati
on)\, but also on specific\nsocially salient subgroups. In this talk\, I w
ill present Outcome\nIndistinguishability (OI)\, a new learning paradigm t
hat draws on the\nconcept of computational indistinguishability. I will\nd
emonstrate that OI can be used to obtain guarantees that go beyond\nstanda
rd loss minimization\, such as simultaneous loss minimization\nacross subg
roups.
DTSTART:20220314T151500Z
DTEND:20220314T161500Z
LAST-MODIFIED:20220314T123428Z
LOCATION:Simonyi 101 and Remote Access
SUMMARY:Computer Science/Discrete Mathematics Seminar I
URL:https://www.ias.edu/math/events/computer-sciencediscrete-mathematics-se
minar-i-504
END:VEVENT
BEGIN:VEVENT
UID:64653332-6231-4232-b662-383366656361
DTSTAMP:20220518T201702Z
CREATED:20211210T162332Z
DESCRIPTION:Topic: Localization schemes: A framework for proving mixing bou
nds for Markov chains\n\nSpeakers: Ronen Eldan\n\nAffiliation: von Neumann
Fellow\, School of Mathematics\n\nTwo recent and seemingly-unrelated tech
niques for proving mixing\nbounds for Markov chains are:\n\n(i) the framew
ork of Spectral Independence\, introduced by Anari\, Liu\nand Oveis Gharan
\, and its numerous extensions\, which have given rise\nto several breakth
roughs in the analysis of mixing times of discrete\nMarkov chains and\n\n(
ii) the Stochastic Localization technique which has proven useful in\nesta
blishing mixing and expansion bounds for both log-concave measures\nand fo
r measures on the discrete hypercube. \n\nWe will present a framework whic
h connects ideas from both techniques\nand by doing so unifies\, simplifie
s and extends those techniques\,\nproviding an approach that works in both
discrete and continuous\nsettings. In its center is the concept of a ``lo
calization scheme''\nwhich\, to every probability measure on some space $\
Omega$ (which will\nusually be either the discrete hypercube or $R^n$\, as
signs a\nmartingale of probability measures which ``localize'' in space as
time\nevolves. As it turns out\, to every such scheme corresponds a Mark
ov\nchain\, and many chains of interest appear naturally in this\nframewor
k. This viewpoint provides tools for deriving mixing bounds\nfor the dyna
mics through the analysis of the corresponding\nlocalization process. Gen
eralizations of concepts of Spectral\nIndependence and Entropic Independen
ce naturally arise from our\ndefinitions\, and in particular we will show
how to recover the main\ntheorems in the spectral and entropic independenc
e frameworks via\nsimple martingale arguments (completely bypassing the ne
ed to use the\ntheory of high-dimensional expanders). We demonstrate how
to apply\nour machinery towards simple proofs to many mixing bounds in the
\nrecent literature. In particular\, we will discuss how to use it to\nobt
ain the first $O(n \log n)$ bound for mixing time of the\nhardcore-model (
of arbitrary degree) in the tree-uniqueness regime\,\nunder Glauber dynami
cs and to prove a KL-divergence decay bound for\nlog-concave sampling via
the Restricted Gaussian Oracle\, which\nachieves optimal mixing under any
$\exp\left (n\right )$-warm start. \n\nBased on a joint work with Yuansi C
hen.
DTSTART:20220315T143000Z
DTEND:20220315T163000Z
LAST-MODIFIED:20220315T152301Z
LOCATION:Simonyi Hall 101 and Remote Access
SUMMARY:Computer Science/Discrete Mathematics Seminar II
URL:https://www.ias.edu/math/events/computer-sciencediscrete-mathematics-se
minar-ii-502
END:VEVENT
BEGIN:VEVENT
UID:32633930-6364-4665-b933-323734393161
DTSTAMP:20220518T201702Z
CREATED:20211027T175334Z
DESCRIPTION:Topic: Online Bipartite Matching and Adwords\n\nSpeakers: Vijay
V. Vazirani\n\nAffiliation: University of California Irvine\n\nOver the l
ast three decades\, the online bipartite matching (OBM)\nproblem has emerg
ed as a central problem in the area of Online\nAlgorithms. Perhaps even mo
re important is its role in the area of\nMatching-Based Market Design. Th
e resurgence of this area\, with the\nrevolutions of the Internet and mobi
le computing\, has opened up novel\,\npath- breaking applications\, and OB
M has emerged as its paradigmatic\nalgorithmic problem. In a 1990 joint p
aper with Richard Karp and\nUmesh Vazirani\, we gave an optimal algorithm\
, called RANKING\, for OBM\,\nachieving a competitive ratio of (1 – 1/e)\;
however\, its analysis\nwas difficult to comprehend. Over the years\, sev
eral researchers\nsimplified the analysis. We will start by presenting a
“textbook\nquality” proof of RANKING. Its simplicity raises the possibilit
y of\nextending RANKING all the way to a generalization of OBM called the
\nadwords problem. This problem is both notoriously difficult and very\ns
ignificant\, the latter because of its role in the AdWords marketplace\nof
Google. We will show how far this endeavor has gone and what\nremains.
We will also provide a broad overview of the area of\nMatching-Based Marke
t Design and pinpoint the role of OBM.\n\nBased on: https://arxiv.org/pdf/
2107.10777.pdf
DTSTART:20220321T151500Z
DTEND:20220321T161500Z
LAST-MODIFIED:20220321T132517Z
LOCATION:Simonyi 101 and Remote Access
SUMMARY:Computer Science/Discrete Mathematics Seminar I
URL:https://www.ias.edu/math/events/computer-sciencediscrete-mathematics-se
minar-i-505
END:VEVENT
BEGIN:VEVENT
UID:32323263-3837-4661-b362-303833306261
DTSTAMP:20220518T201702Z
CREATED:20211210T162345Z
DESCRIPTION:Topic: Localization schemes: A framework for proving mixing bou
nds for Markov chains\n\nSpeakers: Ronen Eldan\n\nAffiliation: von Newmann
Fellow\, School of Mathematics\n\nTwo recent and seemingly-unrelated tech
niques for proving mixing\nbounds for Markov chains are:\n\n(i) the framew
ork of Spectral Independence\, introduced by Anari\, Liu\nand Oveis Gharan
\, and its numerous extensions\, which have given rise\nto several breakth
roughs in the analysis of mixing times of discrete\nMarkov chains and\n\n(
ii) the Stochastic Localization technique which has proven useful in\nesta
blishing mixing and expansion bounds for both log-concave measures\nand fo
r measures on the discrete hypercube.\n\nWe will present a framework which
connects ideas from both techniques\nand by doing so unifies\, simplifies
and extends those techniques\,\nproviding an approach that works in both
discrete and continuous\nsettings. In its center is the concept of a ``loc
alization scheme''\nwhich\, to every probability measure on some space $\O
mega$ (which will\nusually be either the discrete hypercube or $R^n$\, ass
igns a\nmartingale of probability measures which ``localize'' in space as
time\nevolves. As it turns out\, to every such scheme corresponds a Marko
v\nchain\, and many chains of interest appear naturally in this\nframework
. This viewpoint provides tools for deriving mixing bounds\nfor the dynam
ics through the analysis of the corresponding\nlocalization process. Gene
ralizations of concepts of Spectral\nIndependence and Entropic Independenc
e naturally arise from our\ndefinitions\, and in particular we will show h
ow to recover the main\ntheorems in the spectral and entropic independence
frameworks via\nsimple martingale arguments (completely bypassing the nee
d to use the\ntheory of high-dimensional expanders). We demonstrate how t
o apply\nour machinery towards simple proofs to many mixing bounds in the
\nrecent literature. In particular\, we will discuss how to use it to\nobt
ain the first $O(n \log n)$ bound for mixing time of the\nhardcore-model (
of arbitrary degree) in the tree-uniqueness regime\,\nunder Glauber dynami
cs and to prove a KL-divergence decay bound for\nlog-concave sampling via
the Restricted Gaussian Oracle\, which\nachieves optimal mixing under any
$\exp\left (n\right )$-warm start.\n\nBased on a joint work with Yuansi Ch
en.
DTSTART:20220322T143000Z
DTEND:20220322T163000Z
LAST-MODIFIED:20220322T133540Z
LOCATION:Simonyi Hall 101 and Remote Access
SUMMARY:Computer Science/Discrete Mathematics Seminar II
URL:https://www.ias.edu/math/events/computer-sciencediscrete-mathematics-se
minar-ii-503
END:VEVENT
BEGIN:VEVENT
UID:38353861-6437-4333-b365-636263636531
DTSTAMP:20220518T201702Z
CREATED:20211027T175828Z
DESCRIPTION:Topic: Linear cover time is exponentially unlikely\n\nSpeakers:
Quentin Dubroff\n\nAffiliation: Rutgers University\n\nProving a 2009 conj
ecture of Itai Benjamini\, we show: For any C\,\nthere is a > 0 such that
for any simple random walk on an n-vertex\ngraph G\, the probability that
the first Cn steps of the walk hit every\nvertex of G is at most exp[-an]
. A first ingredient of the proof is\na similar statement for Markov chai
ns in which all transition\nprobabilities are less than a suitable functio
n of C. Joint with\nJeff Kahn.
DTSTART:20220328T151500Z
DTEND:20220328T161500Z
LAST-MODIFIED:20220328T122310Z
LOCATION:Simonyi 101 and Remote Access
SUMMARY:Computer Science/Discrete Mathematics Seminar I
URL:https://www.ias.edu/math/events/computer-sciencediscrete-mathematics-se
minar-i-506
END:VEVENT
BEGIN:VEVENT
UID:66393961-6566-4634-a537-613937333030
DTSTAMP:20220518T201702Z
CREATED:20211210T162400Z
DESCRIPTION:Topic: The absorption method\, and an application to an old Ram
sey problem\n\nSpeakers: Matija Bucic\n\nAffiliation: Veblen Research Inst
ructor\, School of Mathematics\n\nThe absorption method is a very simple y
et surprisingly powerful idea\ncoming from extremal combinatorics which al
lows one to convert\nasymptotic results into exact ones. It has produced a
remarkable\nnumber of success stories in recent years with perhaps the mo
st\nprominent being a proof of the existence of designs. In the first part
\nof the talk\, we will introduce the basic idea behind the method and\nth
en illustrate it by showing how it can be used to prove a modified\nversio
n of a classical theorem of Hajnal and Szemeredi on equitable\ncolorings o
f graphs. In the second part of the talk\, we will see an\napplication of
this result to Ramsey theory. Namely\, we will use it to\nsettle a questio
n of Burr\, Erdos\, and Spencer from 1975 concerning\nRamsey numbers of so
-called copy graphs\, one of the precious few\nclasses of graphs for which
we know the Ramsey number precisely.\n\nBased on joint work with Benny Su
dakov.
DTSTART:20220329T143000Z
DTEND:20220329T163000Z
LAST-MODIFIED:20220329T121303Z
LOCATION:Simonyi Hall 101 and Remote Access
SUMMARY:Computer Science/Discrete Mathematics Seminar II
URL:https://www.ias.edu/math/events/computer-sciencediscrete-mathematics-se
minar-ii-504
END:VEVENT
BEGIN:VEVENT
UID:61396134-3630-4166-a265-616135363032
DTSTAMP:20220518T201702Z
CREATED:20211027T180023Z
DESCRIPTION:Topic: Many Nodal Domains in Random Regular Graphs\n\nSpeakers:
Nikhil Srivastava\n\nAffiliation: University of California\, Berkeley\n\n
A nodal domain of a Laplacian eigenvector of a graph is a maximal\nconnect
ed component where it does not change sign. Sparse random\nregular graphs
have been proposed as discrete toy models of 'quantum\nchaos'\, and it ha
s accordingly been conjectured by Y. Elon and\nexperimentally observed by
Dekel\, Lee\, and Linial that the high energy\neigenvectors of such graphs
have many nodal domains.\n\nWe prove superconstant (in fact\, nearly line
ar in the number of\nvertices) lower bounds on the number of nodal domains
of sparse random\nregular graphs\, for sufficiently large Laplacian eigen
values. The\nproof combines two different notions of eigenvector delocaliz
ation in\nrandom matrix theory as well as tools from graph limits and\ncom
binatorics. This is in contrast to what is known for dense\nErdos-Renyi gr
aphs\, which have been shown to have only two nodal\ndomains with high pro
bability.\n\nJoint work with Shirshendu Ganguly\, Theo McKenzie\, and Sidh
anth\nMohanty.
DTSTART:20220404T151500Z
DTEND:20220404T161500Z
LAST-MODIFIED:20220404T123202Z
LOCATION:Wolfensohn Hall and Remote Access
SUMMARY:Computer Science/Discrete Mathematics Seminar I
URL:https://www.ias.edu/math/events/computer-sciencediscrete-mathematics-se
minar-i-507
END:VEVENT
BEGIN:VEVENT
UID:65633433-3938-4334-a339-653365363666
DTSTAMP:20220518T201702Z
CREATED:20211210T162413Z
DESCRIPTION:Topic: A magnetic interpretation of the nodal count on graphs\n
\nSpeakers: Lior Alon\n\nAffiliation: Member\, School of Mathematics\n\nTh
e study of nodal sets\, i.e. zero sets of eigenfunctions\, on\ngeometric o
bjects can be traced back to De Vinci\, Galileo\, Hook\, and\nChladni. Tod
ay it is a central subject of spectral geometry. Sturm\n(1836) showed that
the n-th eigenfunction of the Laplacian on a\nfinite interval has n-1 zer
os\, i.e. nodal points. Fiedler (1975)\nproved a similar result for the di
screte Laplacian of finite tree\ngraphs. However\, if a graph is not a tre
e\, the nodal count may deviate\nfrom n-1. We call this deviation the noda
l surplus. Berkolaiko (2007)\nshowed that the nodal surplus is bounded bet
ween 0 and the first Betti\nnumber of the graph. In 2013 Berkolaiko provid
ed a magnetic\ninterpretation to the nodal surplus. The nodal surplus of
an\neigenvector is equal to the Morse index of its eigenvalue under\nmagne
tic (or twisting) small perturbations of the Laplacian matrix.\nIn this ta
lk I will describe a different proof for this result\, that\nwas given by
Colin de Verdiere (2013)\, and hold for any real symmetric\nmatrix with no
n-positive off-diagonal entries. I will also explain how\nthis naturally e
xtends to any real symmetric matrix\, by modifying the\nnodal count. In th
e last part of the talk\, I will present some\nnumerical experiments sugge
sting that the nodal surplus of large\nrandom graphs should have universal
Gaussian distribution. The talk\nshould be approachable without any need
ed background.
DTSTART:20220405T143000Z
DTEND:20220405T163000Z
LAST-MODIFIED:20220405T123337Z
LOCATION:Wolfensohn Hall and Remote Access
SUMMARY:Computer Science/Discrete Mathematics Seminar II
URL:https://www.ias.edu/math/events/computer-sciencediscrete-mathematics-se
minar-ii-505
END:VEVENT
BEGIN:VEVENT
UID:37396365-3361-4162-b463-303936326463
DTSTAMP:20220518T201702Z
CREATED:20211027T180248Z
DESCRIPTION:Topic: The Long Arm of Theoretical Computer Science: A Case Stu
dy in Blockchains/Web3\n\nSpeakers: Tim Roughgarden\n\nAffiliation: Columb
ia University\n\nBlockchains that support a general contract layer (e.g.\,
Ethereum)\nexport the functionality of a general-purpose\, ownerless\, an
d\nopen-access computer that can enforce property rights for digital\ndata
. How is such functionality implemented? Using a lot of\nextremely cool
computer science ideas! And like everywhere else in\ncomputer science\, t
heory plays an undeniable role in the understanding\nand advancement of th
is technology. In this talk\, I'll highlight\nthree examples (among many)
:\n\n * Possibility and impossibility results for permissionless consensus
\n(i.e.\, implementing an 'ownerless' computer).\n * Incentive-compatible
transaction fee mechanism design (part of\nimplementing an 'open-access' c
omputer).\n * Succinct proofs of computation (for boosting the computer's
power\nby piggybacking on off-chain computation).\n\nParts of this talk ar
e based on joint work with Andrew Lewis-Pye.
DTSTART:20220411T151500Z
DTEND:20220411T161500Z
LAST-MODIFIED:20220411T211907Z
LOCATION:Simonyi 101 and Remote Access
SUMMARY:Computer Science/Discrete Mathematics Seminar I
URL:https://www.ias.edu/math/events/computer-sciencediscrete-mathematics-se
minar-i-508
END:VEVENT
BEGIN:VEVENT
UID:35343161-6262-4662-a166-646265376531
DTSTAMP:20220518T201702Z
CREATED:20211210T162428Z
DESCRIPTION:Topic: Multi-group fairness\, loss minimization and indistingui
shability\n\nSpeakers: Parikshit Gopalan\n\nAffiliation: VMware Research\n
\nTraining a predictor to minimize a loss function fixed in advance is\nth
e dominant paradigm in machine learning. However\, loss minimization\nby i
tself might not guarantee desiderata like fairness and accuracy\nthat one
could reasonably expect from a predictor. To remedy this\,\nmulti-group fa
irness notions such as multiaccuracy and\nmulticalibration have been propo
sed\, which require the predictor to\nshare certain statistical properties
of the _ground truth_\, even\nwhen conditioned on a rich family of subgro
ups. There is no explicit\nattempt at loss minimization.\n\nIn this talk\,
we will describe some recently discovered connections\nbetween loss minim
ization and multi-group fairness. We will explore\nsettings where one can
lead to the other\, and other settings where\nthis is unlikely. We will se
e how the quest for more efficiently\ncomputable notions of multigroup fai
rness leads to natural analogies\nwith the complexity theoretic notions of
indistinguishability and\nderandomization\, where the goal is for our pre
dictor to\nreplicate certain desirable properties of the ground truth.\n\n
In doing so\, we will introduce some novel notions such as that of an\nomn
ipredictor\, whose predictions are simultaneously 'optimal' for a\nlarge c
lass of loss functions and hypothesis\, and low-degree\nmulticalibration\,
which interpolates smoothly between multiaccuracy\nand multicalibration\,
and can be viewed as an analog of the notion of\nbounded independence in
pseudorandomness. \n\nThis is based on joint works with Adam Kalai\, Mic
hael Kim\, Omer\nReingold\, Vatsal Sharan\, Mihir Singhal\, Udi Wieder and
Shengjia\nZhao.
DTSTART:20220412T143000Z
DTEND:20220412T163000Z
LAST-MODIFIED:20220412T122426Z
LOCATION:Simonyi Hall 101 and Remote Access
SUMMARY:Computer Science/Discrete Mathematics Seminar II
URL:https://www.ias.edu/math/events/computer-sciencediscrete-mathematics-se
minar-ii-506
END:VEVENT
BEGIN:VEVENT
UID:36633632-6535-4134-a330-303630316232
DTSTAMP:20220518T201702Z
CREATED:20220215T133709Z
DESCRIPTION:Topic: Set Chasing\, with an application to online shortest pat
h \n\nSpeakers: Sébastien Bubeck\n\nAffiliation: Microsoft Research Lab -
Redmond\n\nSince the late 19th century\, mathematicians have realized the
\nimportance and generality of selection problems: given a collection of\n
sets\, select an element in each set\, possibly in a ``nice” way. Of\npar
ticular importance in computer science is the scenario where the\nground s
et is a metric space\, in which case it is natural to ask for\n*LIPSCHITZ*
selection (with Hausdorff distance between sets). In this\ntalk\, I will
describe a far-reaching extension of this classical\nLipschitz selection p
roblem to an *ONLINE* setting\, where sets are\nstreaming to the selector.
I will show how Riemannian gradient\ndescent (aka mirror descent) can be
used to approach this type of\nproblems. I will illustrate the power of
the framework by solving a\nlong-standing problem in online shortest path
known as layered graph\ntraversal (introduced by Papadimitriou and Yannaka
kis in 1989).
DTSTART:20220418T151500Z
DTEND:20220418T164500Z
LAST-MODIFIED:20220418T141645Z
LOCATION:Simonyi 101 and Remote Access
SUMMARY:Computer Science/Discrete Mathematics Seminar I
URL:https://www.ias.edu/math/events/computer-sciencediscrete-mathematics-se
minar-i-509
END:VEVENT
BEGIN:VEVENT
UID:64613066-3234-4233-a661-646462636632
DTSTAMP:20220518T201702Z
CREATED:20220317T121834Z
DESCRIPTION:Topic: A Tutorial on Gaussian Elimination\n\nSpeakers: John C U
rschel\n\nAffiliation: Member\, School of Mathematics\n\nGaussian eliminat
ion is one of the oldest and most well-known\nalgorithms for solving a lin
ear system. In this talk\, we give a basic\,\nyet thorough overview of the
algorithm\, its variants\, and standard\nerror and conditioning estimates
. In addition\, a number of more modern\nresults and open problems regardi
ng conditioning will be discussed.
DTSTART:20220419T143000Z
DTEND:20220419T163000Z
LAST-MODIFIED:20220419T120654Z
LOCATION:Simonyi Hall 101 and Remote Access
SUMMARY:Computer Science/Discrete Mathematics Seminar II
URL:https://www.ias.edu/math/events/computer-sciencediscrete-mathematics-se
minar-ii-508
END:VEVENT
BEGIN:VEVENT
UID:65373739-6561-4935-b635-393437633934
DTSTAMP:20220518T201702Z
CREATED:20220420T130354Z
DESCRIPTION:Topic: Polynomial Bounds on Parallel Repetition For All 3-Playe
r Games with Binary Inputs\n\nSpeakers: Kunal Mittal\n\nAffiliation: Princ
eton University\n\nUnderstanding the behavior of multi-player (multi-prove
r) games under\nparallel repetition is an important problem in theoretical
computer\nscience.\n\nIn a $k$-player game $G$\, a referee chooses questi
ons $(x^{1}\, ...\,\nx^{k})$ from a (publicly known) distribution $Q$\, an
d for each $j$ in\n${1\, ...\, k}$\, sends the question $x_{j}$ to player
$j$. Then\, each\nplayer $j$\, based on the question they received\, gives
back an answer\n$a^{j}$. Finally\, the referee says whether the players w
in or lose\nbased on the evaluation of a (publicly known) predicate $V(x^{
1}\, ...\,\nx^{k}\, a^{1}\, ...\, a^{k})$. The value of the game is define
d to be the\nmaximum winning probability for the players\, where the maxim
um is over\nthe possible strategies of the players.\n\nIn the n-fold paral
lel repetition $G^{n}$ of the above game\, the\nplayers are given (indepen
dently sampled) questions for $n$ copies of\nthe game and their goal is to
win all copies. More formally\, for each\n$i$ in ${1\, ...\, n}$\, the re
feree samples $(x_{i^{1}}\, ...\,\nx_{i^{k}})$ independently from $Q$. For
each $j$ in ${1\, ...\, k}$\,\nplayer $j$ is given the questions $(x_{1^{
j}}\, ...\, x_{n^{j}})$\, based\non which they answer $(a_{1^{j}}$\, ...\,
$a_{n^{j}})$. The players are\nsaid to win if $V(x_{i^{1}}\, ...\, x_{i^{
k}}$\, $a_{i^{1}}$\, ...\,\n$a_{i^{k}})$ evaluates to true for each ${i}$.
\n\nWhile for every 2-player game G with value $<1$\, the value of the gam
e\n$G^{n}$ is known to decrease exponentially in n (Raz ’98)\, only\ninver
se-Ackerman bounds are known for general k-player games\n(Verbitsky ’96).
\n\nI will talk about some recent progress on this problem\, where we prov
e\nthat for any 3-player game over binary inputs\, with value $<1$\, the\n
value of the n-fold parallel repetition decays polynomially fast to 0.\nAl
ong the way\, we prove two additional parallel repetition theorems\nthat m
ay be of independent interest. We prove polynomial bounds for a\nlarge cla
ss of games\, which we call Playerwise Connected Games\, with\nany number
of players and any input length. This class extends the\nclass of Connecte
d Games of Dinur\, Harsha\, Venkat\, and Yuen ’17 for\nwhich exponential b
ounds are known. We also prove exponential bounds\nfor a 3-player game tha
t we call the Anti-Correlation Game\, which was\nstudied and motivated in
several previous works. In particular\,\nHolmgren and Yang ’19 gave it as
an example for a 3-player game\nwhose non-signaling value is smaller than
1 and yet does not decrease\nat all under parallel repetition\, and thus o
ur result implies an\nexample for a 3-player game where the value of the p
arallel repetition\nof the game behaves completely differently for classic
al strategies\nversus non-signaling strategies.\n\nThis is based on joint
works with Uma Girish\, Justin Holmgren\, Ran\nRaz\, and Wei Zhan.
DTSTART:20220509T151500Z
DTEND:20220509T161500Z
LAST-MODIFIED:20220509T131136Z
LOCATION:Simonyi 101 and Remote Access
SUMMARY:Computer Science/Discrete Mathematics Seminar I
URL:https://www.ias.edu/math/events/computer-sciencediscrete-mathematics-se
minar-i-510
END:VEVENT
BEGIN:VEVENT
UID:61383661-3931-4664-b237-666664313036
DTSTAMP:20220518T201702Z
CREATED:20220505T120244Z
DESCRIPTION:Topic: Association schemes and codes I: The Delsarte linear pro
gram\n\nSpeakers: Leonardo Coregliano\n\nAffiliation: Member\, School of M
athematics\n\nOne of the central problems of coding theory is to determine
the\ntrade-off between the amount of information a code can carry (captur
ed\nby its rate) and its robustness to resist message corruption (captured
\nby its distance). On the existential side\, Gilbert and Varshamov\nshowe
d in the 1950s that random codes and random linear codes achieve\na consid
erably good trade-off\; this is known as the GV bound. On the\nimpossibili
ty side\, McEliece\, Rodemich\, Rumsey and Welch (MRRW) in the\n1970s prov
ided an upper bound\, known as LP bound\, by analyzing the\nDelsarte linea
r programs corresponding to the Hamming and Johnson\nassociation schemes.
However\, there is still a significant gap between\nthese lower and upper
bounds.\n\nIn a recent work with Fernando Jeronimo and Chris Jones\, we pr
ovided a\nhierarchy of higher-order Hamming schemes that is complete for l
inear\ncodes. Namely\, in a high enough level of the hierarchy the\ncorres
ponding Delsarte linear program gives tight bounds for the size\nof linear
codes.\n\nIn this first lecture\, I will go over the basics of the theory
of\nassociation schemes needed to understand our result (and as such no\n
prior knowledge of this theory is required).
DTSTART:20220510T143000Z
DTEND:20220510T163000Z
LAST-MODIFIED:20220510T122256Z
LOCATION:Simonyi Hall 101 and Remote Access
SUMMARY:Computer Science/Discrete Mathematics Seminar II
URL:https://www.ias.edu/math/events/computer-sciencediscrete-mathematics-se
minar-ii-509
END:VEVENT
BEGIN:VEVENT
UID:34303333-3963-4764-a437-653035356564
DTSTAMP:20220518T201702Z
CREATED:20220503T154148Z
DESCRIPTION:Topic: Thresholds\n\nSpeakers: Jinyoung Park\n\nAffiliation: St
anford University\n\nThresholds for increasing properties of random struct
ures are a\ncentral concern in probabilistic combinatorics and related are
as. In\n2006\, Kahn and Kalai conjectured that for any nontrivial increas
ing\nproperty on a finite set\, its threshold is never far from its\n'expe
ctation-threshold\,' which is a natural (and often easy to\ncalculate) low
er bound on the threshold.\n\nIn the first talk\, I will introduce the Kah
n-Kalai Conjecture with\nsome motivating examples and then briefly talk ab
out the recent\nresolution of the Kahn-Kalai Conjecture due to Huy Pham an
d myself.\n\nIn the second talk\, I will discuss our proof of the conjectu
re in\ndetails.
DTSTART:20220516T200000Z
DTEND:20220516T210000Z
LAST-MODIFIED:20220516T213204Z
LOCATION:Simonyi 101 and Remote Access
SUMMARY:Computer Science/Discrete Mathematics Seminar I
URL:https://www.ias.edu/math/events/computer-sciencediscrete-mathematics-se
minar-i-511
END:VEVENT
BEGIN:VEVENT
UID:34653465-3835-4331-b232-373031643265
DTSTAMP:20220518T201702Z
CREATED:20220505T120607Z
DESCRIPTION:Topic: Association schemes and codes II: Completeness of the hi
erarchy of high-order Hamming schemes\n\nSpeakers: Leonardo Coregliano\n\n
Affiliation: Member\, School of Mathematics\n\nOne of the central problems
of coding theory is to determine the\ntrade-off between the amount of inf
ormation a code can carry (captured\nby its rate) and its robustness to re
sist message corruption (captured\nby its distance). One of the main metho
ds to prove upper bounds on\nsizes of codes is via the Delsarte linear pro
gram of the Hamming and\nJohnson schemes. Since these bounds are known to
not be tight\, in a\nrecent work with Fernando Jeronimo and Chris Jones\,
we provided a\nhierarchy of high-order Hamming schemes that is complete in
the sense\nthat in a high enough level their Delsarte linear programs pro
vide\ntight bounds for linear codes.\n\nThe completeness of this hierarchy
explores four different views of\nthe underlying optimization problem: th
e first is the Lovász theta\nprime function on the associated graph\, the
second is the original\nview of the hierarchy in which we factor translati
on and permutation\nsymmetries\, the third is an alternative view in which
we factor\ntranslation and linear combination symmetries and the final on
e builds\non top of the third one by changing bases via Möbius inversion.
\n\nIn this second lecture\, I will cover all these views of the hierarchy
\nand how they come together to prove its completeness.
DTSTART:20220517T143000Z
DTEND:20220517T163000Z
LAST-MODIFIED:20220517T113034Z
LOCATION:Simonyi Hall 101 and Remote Access
SUMMARY:Computer Science/Discrete Mathematics Seminar II
URL:https://www.ias.edu/math/events/computer-sciencediscrete-mathematics-se
minar-ii-510
END:VEVENT
END:VCALENDAR