BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//85f20b73fecb3e0e6ca434791a2aea4a.ias.edu//NONSGML kigkonsult.se i
Calcreator 2.29.14//
CALSCALE:GREGORIAN
UID:e000428b-e342-400f-8040-36ca934cb1b2
X-WR-TIMEZONE:UTC
X-WR-CALNAME:IAS CSDM Seminars
BEGIN:VEVENT
UID:b14183fc-61e1-45e7-88ad-1473d6980aa9
DTSTAMP:20200705T150001Z
CREATED:20200403T114109Z
DESCRIPTION:Topic: Borrowing memory that's being used: catalytic approaches
to the Tree Evaluation Problem\n\nSpeaker: James Cook\, University of Tor
onto\n\nVideo: https://video.ias.edu/csdm/2020/0406-JamesCook\n\nI'll be p
resenting some joint work with Ian Mertz scheduled to appear at STOC 2020.
\n\nThe study of the Tree Evaluation Problem (TEP)\, introduced by S. Cook
et al. (TOCT 2012)\, is a promising approach to separating L from P. Give
n a label in [k] at each leaf of a complete binary tree and an explicit fu
nction [k]^2 -> [k] for recursively computing the value of each internal n
ode from its children\, the problem is to compute the value at the root no
de. A simple recursive algorithm can solve this using Theta(h log k) memor
y\, where h is the tree height and k is the size of the alphabet. Until no
w\, no better deterministic algorithm was known.\n\nWe present a new algor
ithm which uses less memory when k is not too big compared to h\, inspired
by a surprising result from Burhman et al. about “catalytic space' comput
ation (STOC 2012). Ours is the first algorithm to beat the simple recursiv
e algorithm\, and also the first non-trivial approach to proving a determi
nistic upper bound for TEP.
DTSTART:20200406T150000Z
DTEND:20200406T160000Z
LAST-MODIFIED:20200407T135221Z
LOCATION:https://theias.zoom.us/j/360043913
SUMMARY:Computer Science/Discrete Mathematics Seminar I
URL:https://www.ias.edu/node/110381
END:VEVENT
BEGIN:VEVENT
UID:7c59d91b-baa8-4f23-9b34-c5b6216db9f0
DTSTAMP:20200705T150001Z
CREATED:20190607T203002Z
DESCRIPTION:Topic: Primality testing\n\nSpeaker: Andrey Kupavskii \, Member
\, School of Mathematics\n\nVideo: https://video.ias.edu/csdm/2020/0407-An
dreyKupavskii\n\nIn the talk\, I will explain the algorithm (and its analy
sis) for testing whether a number is a prime\, invented by Agrawal\, Kayal
\, and Saxena.
DTSTART:20200407T143000Z
DTEND:20200407T163000Z
LAST-MODIFIED:20200408T163016Z
LOCATION:https://theias.zoom.us/j/360043913
SUMMARY:Computer Science/Discrete Mathematics Seminar II
URL:https://www.ias.edu/node/100681
END:VEVENT
BEGIN:VEVENT
UID:0f4df45c-442d-432f-8f66-8a09ddf90178
DTSTAMP:20200705T150001Z
CREATED:20200409T143458Z
DESCRIPTION:Topic: Legal Theorems of Privacy\n\nSpeaker: Kobbi Nissim\, Geo
rgetown University\n\nVideo: https://video.ias.edu/csdm/2020/0410-KobbiNis
sim\n\nThere are significant gaps between legal and technical thinking aro
und data privacy. Technical standards such as k-anonymity and differential
privacy are described using mathematical language whereas legal standards
are not rigorous from a mathematical point of view and often resort to co
ncepts such as de-identification and anonymization which they only partial
ly define. As a result\, arguments about the adequacy of technical privacy
measures for satisfying legal privacy often lack rigor\, and their conclu
sions are uncertain. The uncertainty is exacerbated by a litany of success
ful privacy attacks on privacy measures thought to meet legal expectations
but then shown to fall short of doing so. In this work\, we ask whether i
t is possible to introduce mathematical rigor into such analyses to the po
int of making and proving formal “legal theorems” that certain technical p
rivacy measures meet legal expectations. For that\, we explore some of the
gaps between these two very different approaches\, and present initial st
rategies towards bridging these gaps considering examples from US and EU l
aw.\n\nBased on work with Aloni Cohen
DTSTART:20200413T150000Z
DTEND:20200413T160000Z
LAST-MODIFIED:20200413T194553Z
LOCATION:https://theias.zoom.us/j/360043913
SUMMARY:Computer Science/Discrete Mathematics Seminar I
URL:https://www.ias.edu/node/110436
END:VEVENT
BEGIN:VEVENT
UID:21891bd0-9b77-4fdf-9f7d-5f5cb8d3999e
DTSTAMP:20200705T150001Z
CREATED:20200415T175351Z
DESCRIPTION:Topic: Structure vs Randomness in Complexity Theory\n\nSpeaker:
Rahul Santhanam\, University of Oxford\n\nVideo: https://video.ias.edu/cs
dm/2020/0420-RahulSanthanam\n\nThe dichotomy between structure and randomn
ess plays an important role in areas such as combinatorics and number theo
ry. I will discuss a similar dichotomy in complexity theory\, and illustra
te it with three examples of my own work: (i) An algorithmic result (with
Igor Oliveira) showing how to probabilistically generate a fixed prime of
length n in time sub-exponential in n\, for infinitely many n (ii) A lower
bound result showing that Promise-MA\, the class of promise problems with
short proofs that are verifiable efficiently by probabilistic algorithms\
, does not have circuits of size n^k for any fixed k (iii) A barrier resul
t (with Jan Pich) showing that certain lower bounds in proof complexity ar
e not themselves efficiently provable.\n\nWhat these results all have in c
ommon is that they are unconditional results in settings where such result
s are often surprising\, and that the proofs are non-constructive. I will
speculate on whether this non-constructivity is essential\, and on the imp
lications for complexity theory more broadly.
DTSTART:20200420T150000Z
DTEND:20200420T160000Z
LAST-MODIFIED:20200421T174647Z
LOCATION:https://theias.zoom.us/j/360043913
SUMMARY:Computer Science/Discrete Mathematics Seminar I
URL:https://www.ias.edu/node/110561
END:VEVENT
BEGIN:VEVENT
UID:76ee2717-320e-4e55-b0c6-64e473d654bb
DTSTAMP:20200705T150001Z
CREATED:20200415T175900Z
DESCRIPTION:Topic: Non-commutative optimization: theory\, algorithms and ap
plications (or\, can we prove P!=NP using gradient descent)\n\nSpeaker: A
vi Wigderson\, Herbert H. Maass Professor\, School of Mathematics\n\nVideo
: https://video.ias.edu/csdm/2020/0421-AviWigderson\n\nThis talk aims to s
ummarize a project I was involved in during the past 5 years\, with the ho
pe of explaining our most complete understanding so far\, as well as chall
enges and open problems. The main messages of this project are summarized
below\; I plan to describe\, through examples\, many of the concepts they
refer to\, and the evolution of ideas leading to them. No special backgrou
nd is assumed.\n\n(1) The most basic tools of convex optimization in Eucli
dean space extend to a far more general setting of Riemannian manifolds th
at arise from the symmetries of non-commutative groups. We develop first-o
rder and second-order algorithms\, and analyze their performance in genera
l. While proving convergence bounds requires heavy algebraic and analytic
tools\, convergence itself depends in an elegant way on natural ``smoothne
ss’’ parameters\, in analogy with the Euclidean (commutative) case.\n\n(2)
These algorithms give exponential time (or better) improvements for solvi
ng algorithmic many problems across CS\, Math and Physics. In particular\,
these include problems in algebra (e.g. testing rational identities in no
n-commutative variables)\, in analysis (testing the feasibility and tightn
ess of Brascamp-Lieb inequalities)\, in quantum information theory (to the
quantum marginals problem)\, in algebraic geometry (to computing Kronecke
r coefficients)\, in computational complexity (to derandomizing new specia
l cases of the PIT problem) and in optimization (to testing membership in
large implicitly described polytopes).\n\n(3) The focus on symmetries expo
se old and reveal new relations between the problems above. Essentially\,
they are all membership problems in null cones and moment polytopes of nat
ural group actions on natural spaces. Invariant theory\, which studies suc
h group actions\, plays an essential role in this development. In particul
ar\, a beautiful non-commutative duality theory (expending linear programm
ing duality in the commutative case)\, and notions of geodesic convexity (
extending the Euclidean one) and moment maps (extending the Euclidean grad
ient) are central to the algorithms and their analysis. Interestingly\, mo
st algorithms in invariant theory are symbolic/algebraic\, and these new n
umeric/analytic algorithms proposed here often significntly improve on the
m.\n\nBased on joint works with Zeyuan Allen-Zhu\, Peter Burgisser\, Cole
Franks\, Ankit Garg\, Leonid Gurvits\, Pavel Hrubes\, Yuanzhi Li\, Visu Ma
kam\, Rafael Oliveira and Michael Walter.
DTSTART:20200421T143000Z
DTEND:20200421T163000Z
LAST-MODIFIED:20200421T223631Z
LOCATION:https://theias.zoom.us/j/360043913
SUMMARY:Computer Science/Discrete Mathematics Seminar II
URL:https://www.ias.edu/node/110566
END:VEVENT
BEGIN:VEVENT
UID:c9fcaf15-8c77-470d-bda5-4dafc5f5e8af
DTSTAMP:20200705T150001Z
CREATED:20200219T150300Z
DESCRIPTION:Topic: Graph and Hypergraph Sparsification\n\nSpeaker: Luca Tre
visan\, Bocconi University\n\nVideo: https://video.ias.edu/csdm/2020/0427-
LucaTrevisan\n\nA weighted graph H is a sparsifier of a graph G if H has m
uch fewer edges than G and\, in an appropriate technical sense\, H 'approx
imates' G. Sparsifiers are useful as compressed representations of graphs
and to speed up certain graph algorithms. In a 'cut sparsifier\,' the noti
on of approximation is that every cut is crossed by approximately the same
number of edges in G as in H. In a 'spectral sparsifier' a stronger\, lin
ear-algebraic\, notion of approximation holds. Similar definitions can be
given for hypergraphs. We discuss some new definitions\, new constructions
and new lower bounds for graph and hypergraph sparsifiers\, including: -
A new lower bound on the number edges of any spectral sparsifier\, which c
an be seen as a generalization of the Alon-Boppana theorem to graphs that
are irregular and weighted\; - A new lower bound on the number of bits nee
ded for any data structure that approximately stores the cut information o
f the graph\, showing that known sparsifiers optimally solve this data str
ucture problem - A new definition and constructions of sparsification for
graph and hypergraphs\, which allows *unweighted* sparsifiers with O(n) ed
ges for all graphs and hypergraphs - A new construction of spectral hyperg
raph sparsifiers with a nearly-linear number of hyperedges (compared to a
cubic number of hyperedges in previous constructions).\n\nBased on joint w
ork with Nikhil Bansal\, Charles Carlson\, Alexandra Kolla\, Nikhil Srivas
tava and Ola Svensson.
DTSTART:20200427T150000Z
DTEND:20200427T160000Z
LAST-MODIFIED:20200427T194707Z
LOCATION:https://theias.zoom.us/j/360043913
SUMMARY:Computer Science/Discrete Mathematics Seminar I
URL:https://www.ias.edu/node/109426
END:VEVENT
BEGIN:VEVENT
UID:f6d69696-5e0b-4dcb-9142-a5051f7f6806
DTSTAMP:20200705T150001Z
CREATED:20200420T143537Z
DESCRIPTION:Topic: A Framework for Quadratic Form Maximization over Convex
Sets\n\nSpeaker: Vijay Bhattiprolu\, Member\, School of Mathematics\n\nVid
eo: https://video.ias.edu/csdm/2020/0428-VijayBhattiprolu\n\nWe investigat
e the approximability of the following optimization problem\, whose input
is an\nn-by-n matrix A and an origin symmetric convex set C that is given
by a membership oracle:\n'Maximize the quadratic form as x ranges over C.
'\n\nThis is a rich and expressive family of optimization problems\; for d
ifferent choices of forms A\nand convex bodies C it includes a diverse ran
ge of interesting combinatorial and continuous\noptimization problems. To
name some examples\, max-cut\, Grothendieck's inequality\, the\nnon-commut
ative Grothendieck inequality\, certifying hypercontractivity\, small set
expansion\,\nvertex expansion\, and the spread constant of a metric\, are
all captured by this class. While the\nliterature studied these special ca
ses using case-specific reasoning\, here we develop a general\nmethodology
for treatment of the approximability and inapproximability aspects of the
se questions.\n\nBased on joint work with Euiwoong Lee and Assaf Naor.
DTSTART:20200428T143000Z
DTEND:20200428T163000Z
LAST-MODIFIED:20200428T233250Z
LOCATION:https://theias.zoom.us/j/360043913
SUMMARY:Computer Science/Discrete Mathematics Seminar II
URL:https://www.ias.edu/node/110636
END:VEVENT
BEGIN:VEVENT
UID:a5ec3207-0ca8-451e-9868-6d67997090a5
DTSTAMP:20200705T150001Z
CREATED:20200423T124043Z
DESCRIPTION:Topic: Local Statistics\, Semidefinite Programming\, and Commun
ity Detection\n\nSpeaker: Prasad Raghavendra\, University of California\,
Berkeley\n\nVideo: https://video.ias.edu/csdm/2020/0504-PrasadRaghavendra
\n\nWe propose a new hierarchy of semidefinite programming relaxations for
inference problems. As test cases\, we consider the problem of community
detection in block models. The vertices are partitioned into k communities
\, and a graph is sampled conditional on a prescribed number of inter- and
intra-community edges. The problem of detection\, where we are to decide
with high probability whether a graph was drawn from this model or the uni
form distribution on regular graphs\, is conjectured to undergo a computat
ional phase transition at a point called the Kesten-Stigum (KS) threshold.
We consider two models of random graphs namely the well-studied (irregula
r) stochastic block model and a distribution over random regular graphs we
'll call the degree-regular block model (DRBM). For both these models\, we
show that sufficiently high constant levels of our hierarchy can perform
detection arbitrarily close to the KS threshold and that our algorithm is
robust to up to a linear number of adversarial edge perturbations. Further
more\, in the case of DRBM\, we show that below the Kesten-Stigum threshol
d no constant level can do so.\n\nJoint work with Jess Banks (U.C.Berkeley
) and Sidhanth Mohanty (U.C. Berkeley)
DTSTART:20200504T150000Z
DTEND:20200504T160000Z
LAST-MODIFIED:20200505T140304Z
LOCATION:https://theias.zoom.us/j/360043913
SUMMARY:Computer Science/Discrete Mathematics Seminar I
URL:https://www.ias.edu/node/110681
END:VEVENT
BEGIN:VEVENT
UID:9d98a228-3f6b-4d9b-9730-b314ac8e4503
DTSTAMP:20200705T150001Z
CREATED:20200423T184154Z
DESCRIPTION:Topic: Recent Progress on Cutting Planes Proofs\n\nSpeaker: Noa
h Fleming\, University of Toronto\n\nVideo: https://video.ias.edu/csdm/202
0/0505-NoahFleming\n\nProof Complexity studies the length of proofs of pro
positional tautologies in various restricted proof systems. One of the mos
t well-studied is the Cutting Planes proof system\, which captures reasoni
ng which can be expressed using linear inequalities. A series of papers pr
oved lower bounds on the length of Cutting Planes using the method of feas
ible interpolation whereby proving lower bounds on the size of Cutting Pla
nes lower bounds proofs of a certain restricted class of formulas is reduc
ed to monotone circuit lower bounds. However\, it was not known how to obt
ain lower bounds for more natural formulas such as the Tseitin (mod 2) for
mulas or random formulas.\n\nIn this talk I will discuss two recent result
s for Cutting Planes. The first is joint work together with Pankratov\, Pi
tassi\, and Robere (and proved independently by Hrubeš and Pudlak) which p
roves exponential lower bounds on the length of Cutting Planes proofs of r
andom Θ(log n)-CNF formulas. The second is a surprising result of Dadush a
nd Tiwari which gives quasi-polynomial size Cutting Planes proofs of the T
seitin tautologies. My aim is to highlight the main conceptual ideas in th
e proofs of both of these results.
DTSTART:20200505T143000Z
DTEND:20200505T163000Z
LAST-MODIFIED:20200505T140404Z
LOCATION:https://theias.zoom.us/j/360043913
SUMMARY:Computer Science/Discrete Mathematics Seminar II
URL:https://www.ias.edu/node/110741
END:VEVENT
BEGIN:VEVENT
UID:a18e4f29-c81c-4989-bc3f-970af19351a0
DTSTAMP:20200705T150001Z
CREATED:20200124T160538Z
DESCRIPTION:Topic: Using discrepancy theory to improve the design of random
ized controlled trials\n\nSpeaker: Daniel Spielman\, Yale University\n\nVi
deo: https://video.ias.edu/csdm/2020/0511-DanielSpielman\n\nIn randomized
experiments\, such as a medical trials\, we randomly assign the treatment\
, such as a drug or a placebo\, that each experimental subject receives. R
andomization can help us accurately estimate the difference in treatment e
ffects with high probability. We also know that we want the two groups to
be similar: ideally the two groups would be similar in every statistic we
can measure beforehand. Recent advances in algorithmic discrepancy theory
allow us to divide subjects into groups with similar statistics.\n\nBy exp
loiting the Gram-Schmidt Walk algorithm of Bansal\, Dadush\, Garg\, and Lo
vett\, we can obtain random assignments of low discrepancy. These allow us
to obtain more accurate estimates of treatment effects when the informati
on we measure about the subjects is predictive\, while also bounding the w
orst-case behavior when it is not.\n\nIn this talk\, I will formally expla
in the problem of estimating treatment effects in randomized controlled tr
ials\, the dangers of using fancy inference techniques instead of fancy de
signs\, how we use the Gram-Schmidt Walk algorithm\, a tight analysis of t
his algorithm\, and how we use it to obtain confidence intervals. I hope t
o explain just how much we don't yet know.\n\nThis is joint work with Chri
stopher Harshaw\, Fredrik Sävje\, and Peng Zhang.
DTSTART:20200511T150000Z
DTEND:20200511T160000Z
LAST-MODIFIED:20200515T011654Z
LOCATION:https://theias.zoom.us/j/360043913
SUMMARY:Computer Science/Discrete Mathematics Seminar I
URL:https://www.ias.edu/node/108111
END:VEVENT
BEGIN:VEVENT
UID:20429466-b2cf-49c5-b157-fec37ef6ffb6
DTSTAMP:20200705T150001Z
CREATED:20200423T184346Z
DESCRIPTION:Topic: Convex Set Disjointness\, Distributed Learning of Halfsp
aces\, and Linear Programming\n\nSpeaker: Shay Moran\, Member\, School of
Mathematics\n\nVideo: https://video.ias.edu/csdm/2020/0512-ShayMoran\n\nDi
stributed learning protocols are designed to train on distributed data wit
hout gathering it all on a single centralized machine\, thus contributing
to the efficiency of the system and enhancing its privacy. We study a cent
ral problem in distributed learning\, called Distributed Learning of Halfs
paces: let U \subset R^d be a known domain of size n and let h:R^d —> R be
an unknown target affine function. A set of examples {(u\,b)} is distribu
ted between several parties\, where u \in U is a point and b = sign(h(u))
\in {-1\, +1} is its label. The parties' goal is to agree\, using minimum
communication\, on a classifier f: U—>{-1\,+1} such that f(u)=b for every
input example (u\,b). (In practice\, the finite domain U is defined implic
itly by the representation of d-dimensional vectors which is used in the p
rotocol.) We establish a (nearly) tight bound of ~$\Theta$ (d*log n) on th
e communication complexity of the problem of distributed learning of halfs
paces in the two-party setting. Since this problem is closely related to t
he Convex Set Disjointness problem in communication complexity and the pro
blem of Distributed Linear Programming in distributed optimization\, we ar
e able to derive upper and lower bounds of ~O(d^2\log n) and ~Ω(d\log n) f
or both of these basic problems as well. Our main technical contribution l
ies in the design and analysis of the protocols which imply the upper boun
ds. To this end\, we introduce a technique called Halfspace Containers\, a
llowing for a compressed approximate representation of every halfspace. Ha
lfspace containers may be of independent interest and are closely related
to bracketing numbers in statistics and to hyperplane cuttings in discrete
geometry. Joint paper with Mark Braverman\, Gillat Kol\, and Raghuvansh R
Saxena
DTSTART:20200512T143000Z
DTEND:20200512T163000Z
LAST-MODIFIED:20200515T011733Z
LOCATION:https://theias.zoom.us/j/360043913
SUMMARY:Computer Science/Discrete Mathematics Seminar II
URL:https://www.ias.edu/node/110746
END:VEVENT
BEGIN:VEVENT
UID:9e7c412b-acf1-4b07-a009-05c42aad84ce
DTSTAMP:20200705T150001Z
CREATED:20200423T185014Z
DESCRIPTION:Topic: The Non-Stochastic Control Problem\n\nSpeaker: Elad Haza
n\, Princeton University\n\nVideo: https://video.ias.edu/csdm/2020/0518-El
adHazan\n\nLinear dynamical systems are a continuous subclass of reinforce
ment learning models that are widely used in robotics\, finance\, engineer
ing\, and meteorology. Classical control\, since the work of Kalman\, has
focused on dynamics with Gaussian i.i.d. noise\, quadratic loss functions
and\, in terms of provably efficient algorithms\, known systems and observ
ed state. We'll discuss how to apply new machine learning methods which re
lax all of the above: efficient control with adversarial noise\, general l
oss functions\, unknown systems\, and partial observation.\n\nBased on a s
eries of works with Naman Agarwal\, Nataly Brukhim\, Karan Singh\, Sham Ka
kade\, Max Simchowitz\, Cyril Zhang\, Paula Gradu\, John Hallman
DTSTART:20200518T150000Z
DTEND:20200518T160000Z
LAST-MODIFIED:20200518T180314Z
LOCATION:https://theias.zoom.us/j/360043913
SUMMARY:Computer Science/Discrete Mathematics Seminar I
URL:https://www.ias.edu/node/110751
END:VEVENT
END:VCALENDAR