BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//85f20b73fecb3e0e6ca434791a2aea4a.ias.edu//NONSGML kigkonsult.se iCalcreator 2.41.71//
CALSCALE:GREGORIAN
UID:30323637-3536-4230-b238-333164383361
X-WR-TIMEZONE:UTC
X-WR-CALNAME:IAS CSDM Seminars
BEGIN:VEVENT
UID:37366533-3838-4566-a534-306635343566
DTSTAMP:20230209T063950Z
CREATED:20220808T183211Z
DESCRIPTION:Topic: Communication and Query Complexity of Bipartite Perfect
Matching\n\nSpeakers: Yuval Efron\n\nAffiliation: Columbia University\n\nI
n this talk\, I'll discuss a recent result where we settle the\ncomplexiti
es of the maximum-cardinality bipartite matching problem\n(BMM) up to poly
-logarithmic factors in five models of computation: \nThe two-party commun
ication\, AND query\, OR query\, XOR query\, and\nquantum edge query model
s. Our results answer open problems that\nhave been raised repeatedly sin
ce at least three decades ago [Hajnal\,\nMaass\, and Turan STOC’88\; Ivany
os\, Klauck\, Lee\, Santha\, and de Wolf\nFSTTCS’12\; Dobzinski\, Nisan\,
and Oren STOC’14\; Nisan SODA’21]\nand tighten the lower bounds shown by B
eniamini and Nisan [STOC’21]\nand Zhang [ICALP’04]. We also settle the co
mmunication complexity\nof the generalizations of BMM\, such as maximum-co
st bipartite\nb-matching and transshipment\; and the query complexity of u
nique\nbipartite perfect matching (answering an open question by Beniamini
\n[2022]). Our algorithms and lower bounds follow from simple\napplicatio
ns of known techniques such as cutting planes methods and\nset disjointnes
s. Lastly\, I'll discuss some cool open problems!\n\nBased on joint work
with Joakim Blikstad\, Jan van den Brand\, Sagnik\nMukhopadhyay & Danupon
Nanongkai from FOCS 2022.
DTSTART:20221114T161500Z
DTEND:20221114T171500Z
LAST-MODIFIED:20221129T200225Z
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-521
END:VEVENT
BEGIN:VEVENT
UID:62376139-3937-4839-b761-306136306538
DTSTAMP:20230209T063950Z
CREATED:20220808T191912Z
DESCRIPTION:Speakers: Toniann Pitassi\n\nAffiliation: University of Toronto
and Columbia University\; Visiting Professor\, School of Mathematics\n\nI
n this talk I will first review some basics about communication\ncomplexit
y. Secondly I will survey some (old and new) equivalences\nbetween centra
l problems in communication complexity and related\nquestions in additive
combinatorics. In particular\, we will\nreformulate a few questions in ad
ditive combinatorics\n(Arithmetic Progressions\, Corners Theorem\, Hales-J
ewitt Theorem\, and\ndense Ruzsa-Szemeredi graphs) as equivalent questions
in\ncommunication complexity. I will then discuss some recent progress on
\nthe Corners problem\, based on this connection.
DTSTART:20221115T153000Z
DTEND:20221115T173000Z
LAST-MODIFIED:20221129T200256Z
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-518
END:VEVENT
BEGIN:VEVENT
UID:35356434-6662-4134-a136-303833313561
DTSTAMP:20230209T063950Z
CREATED:20220808T183247Z
DESCRIPTION:Topic: Strong XOR Lemma for Communication with Bounded Rounds\n
\nSpeakers: Huacheng Yu\n\nAffiliation: Princeton University\n\nIn this ta
lk\, we show a strong XOR lemma for bounded-round two-player\nrandomized c
ommunication. For a function f:X×Y→{0\,1}\, the\nn-fold XOR function f^⊕n
:X^n×Y^n→{0\,1} maps n input pairs\n(x_1\,...\,x_n)\, (y_1\,...\,y_n) to t
he XOR of the n output bits\nf(x_1\,y_1)⊕...⊕f(x_n\, y_n). We prove that
if every r-round\ncommunication protocols that computes f with probability
2/3 uses at\nleast C bits of communication\, then any r-round protocol th
at\ncomputes f^⊕n with probability 1/2+exp(-O(n)) must use\nn(r^{-O (r)}C-
1) bits. When r is a constant and C is sufficiently\nlarge\, this is Omeg
a(nC) bits. It matches the communication cost\nand the success probabilit
y of the trivial protocol that computes the\nn bits f(x_i\,y_i) independen
tly and outputs their XOR\, up to a\nconstant factor in n. \n\nA similar X
OR lemma has been proved for f whose communication lower\nbound can be obt
ained via bounding the discrepancy [Shaltiel03]. By\nthe equivalence betwe
en the discrepancy and the correlation with\n2-bit communication protocols
\, our new XOR lemma implies the previous\nresult.
DTSTART:20221121T161500Z
DTEND:20221121T171500Z
LAST-MODIFIED:20221129T200329Z
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-522
END:VEVENT
BEGIN:VEVENT
UID:33313465-3364-4161-b664-613335373330
DTSTAMP:20230209T063950Z
CREATED:20220808T191942Z
DESCRIPTION:Topic: The Polynomial Method in Communication Complexity\n\nSpe
akers: Pei Wu\n\nAffiliation: Member\, School of Mathematics\n\nA powerful
technique developed and extended in the past decade in\ncommunication com
plexity is the so-called 'lifting theorems.' The\nidea is to translate th
e hardness results from 'easier' models\, e.g.\,\nquery complexity\, polyn
omial degrees\, to the more challenging\ncommunication model.\n\nIn this t
alk\, I plan to discuss lifting polynomial degrees to\ncommunication lower
bounds. For any boolean function $f: {0\,1}^n \to\n{0\,1}$\, we show ther
e is a constant size gadget g: $X \times Y \to\n{0\,1}$\, such that $f \c
irc g$ has (deterministic\,\nquantum\, unbounded-error probabilistic) comm
unication complexity at\nleast the (exact\, approximate\, and threshold) d
egree of f. This\nparticular technique was developed by Sherstov\, Razboro
v-Sherstov in a\nseries of works.\n\nBesides proving strong communication
lower bounds\, the technique has\napplications in many areas\, especially
circuits complexity.\nHopefully\, we will discuss some of the applications
.'
DTSTART:20221122T153000Z
DTEND:20221122T173000Z
LAST-MODIFIED:20221129T200405Z
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-520
END:VEVENT
BEGIN:VEVENT
UID:63636534-6536-4133-b733-366262656431
DTSTAMP:20230209T063950Z
CREATED:20220808T191800Z
DESCRIPTION:Topic: Algorithmic Stochastic Localization for the Sherrington-
Kirkpatrick Model\n\nSpeakers: Mark Sellke\n\nAffiliation: Member\, School
of Mathematics\n\nSampling from high-dimensional\, multimodal distributio
ns is a\ncomputationally challenging and fundamental task. This talk will
\nfocus on a family of random instances of such problems described by\nran
dom quadratic potentials on the hypercube known as the\nSherrington-Kirkpa
trick model. I will describe an approximate\nsampling algorithm for the h
igh temperature regime as well as matching\nlow-temperature hardness resul
ts stemming from disorder chaos. Our\nalgorithm uses stochastic localizat
ion\, which progressively tilts the\ndesired measure towards a single conf
iguration\, together with an\napproximate message passing algorithm that i
s used to approximate the\nmean of the tilted measure. Based on joint wor
k with Ahmed El Alaoui\nand Andrea Montanari.
DTSTART:20221128T161500Z
DTEND:20221128T171500Z
LAST-MODIFIED:20221129T200435Z
LOCATION:Simonyi Hall 101 and Remote Access
SUMMARY:Computer Science/Discrete Mathematics Seminar I
URL:https://www.ias.edu/math/events/computer-sciencediscrete-mathematics-se
minar-i-527
END:VEVENT
BEGIN:VEVENT
UID:32363132-3963-4363-a331-653731393266
DTSTAMP:20230209T063950Z
CREATED:20220808T192011Z
DESCRIPTION:Topic: The Hypergraph Container Method\, Partition Containers\,
and Algorithmic Applications\n\nSpeakers: Or Zamir\n\nAffiliation: Visito
r\, School of Mathematics\n\nThe recently-discoverd Hypergraph Container M
ethod (Saxton and\nThomason\, Balogh\, Morris and Samotij)\, generalizing
an earlier version\nfor graphs (Kleitman and Winston)\, is used extensivel
y in recent years\nin extremal and probabilistic combinatroics. In essenc
e\, it shows\nthat independent sets in regular-enough dense hypergraphs mu
st be\nclustered in some fashion.\n\nIn this seminar we will give an overv
iew of this method and then\npresent its first algorithmic applications.
We use it\nalgorithmically to convert algorithms into faster algorithms fo
r\nregular or dense input instances. An important component of our work\n
is the generalization of graph containers to Partition Containers. \nWhile
standard containers apply to a single independent set\, partition\ncontai
ners explore the structure of several independent sets at the\nsame time.
\n\nOur main application resolves a major open problem about Graph\nColori
ng algorithms\, for regular graphs. The chromatic number of a\ngraph can
be computed in $2^n$ time (Husfeldt et al.). For $k<=6$ it\nis known that
$k$-coloring can be solved in $(2-eps)^n$ time for some\n$eps>0$. For la
rger values of $k$ improvements are only known for\nsparse graphs. We sho
w that $k$-coloring of regular graphs can be\nsolved in $(2-eps_k)^n$ time
\, where $eps_k>0$ for every $k$. We\nstress that the degree of the regul
ar graphs is unbounded. \n\nAs another application\, we give the first im
proved $k$-SAT algorithm\nfor dense formulas. We give additional applicat
ions including faster\nalgorithms for unweighted and weighted Maximum Inde
pendent Set\nalgorithms in regular graphs.
DTSTART:20221129T153000Z
DTEND:20221129T173000Z
LAST-MODIFIED:20221129T200610Z
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-519
END:VEVENT
BEGIN:VEVENT
UID:66333735-3133-4131-b733-353537363961
DTSTAMP:20230209T063950Z
CREATED:20220808T184501Z
DESCRIPTION:Topic: Optimal Weak to Strong Learning\n\nSpeakers: Kasper Gree
n Larsen\n\nAffiliation: Aarhus University \n\nThe classic algorithm AdaBo
ost allows to convert a weak learner\, that\nis an algorithm that produces
a hypothesis which is slightly better\nthan chance\, into a strong learne
r\, achieving arbitrarily high\naccuracy when given enough training data.
We present a new algorithm\nthat constructs a strong learner from a weak l
earner but uses less\ntraining data than AdaBoost and all other weak to st
rong learners to\nachieve the same generalization bounds. A sample complex
ity lower\nbound shows that our new algorithm uses the minimum possible am
ount of\ntraining data and is thus optimal. Hence\, this work settles the
sample\ncomplexity of the classic problem of constructing a strong learner
\nfrom a weak learner. \n\nThis work was accepted at NeurIPS’22 and is joi
nt work with Martin\nRitzert from Aarhus University\n\n
DTSTART:20221205T161500Z
DTEND:20221205T171500Z
LAST-MODIFIED:20221207T191519Z
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-524
END:VEVENT
BEGIN:VEVENT
UID:61373062-3135-4137-b861-656139303730
DTSTAMP:20230209T063950Z
CREATED:20220808T192039Z
DESCRIPTION:Topic: Online List Labeling: Breaking the log$^2$ n Barrier\n\n
Speakers: Nicole Wein\n\nAffiliation: Rutgers University\n\nThe online lis
t labeling problem is a basic primitive in data\nstructures. The goal is t
o store a dynamically-changing set of n items\nin an array of m slots\, wh
ile keeping the elements in sorted order. To\ndo so\, some items may need
to be moved over time\, and the goal is to\nminimize the number of items m
oved per insertion/deletion. When $m =\nCn$ for some constant $C>1$\, an u
pper bound of $O(log^2 n)$items moved\nper insertion/deletion has been kno
wn since 1981. There is a matching\nlower bound for deterministic algorith
ms\, but for randomized\nalgorithms\, the best known lower bound is Omega(
log n)\, leaving a gap\nbetween upper and lower bounds. We improve the upp
er bound\, providing\na randomized data structure with expected $O(log^{3/
2} n)$ items moved\nper insertion/deletion.\n\nJoint work with Michael Ben
der\, Alexander Conway\, Martin\nFarach-Colton\, Hanna Komlos\, and Willia
m Kuszmaul
DTSTART:20221206T153000Z
DTEND:20221206T173000Z
LAST-MODIFIED:20221207T191544Z
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-521
END:VEVENT
BEGIN:VEVENT
UID:34646661-6132-4664-b331-333239376532
DTSTAMP:20230209T063950Z
CREATED:20220808T184552Z
DESCRIPTION:Topic: Optimization-Friendly Generic Mechanisms Without Money\n
\nSpeakers: Mark Braverman\n\nAffiliation: Princeton University\n\nOur goa
l is to develop a generic framework for converting modern\ngradient-descen
t based optimization algorithms into mechanisms where\ninputs come from se
lf-interested agents.\n\nWe focus on aggregating preferences from n player
s in a context\nwithout money. Special cases of this setting include votin
g\,\nallocation of items by lottery\, and matching. Our key technical\ncon
tribution is a new meta-algorithm we call APEX (Adaptive Pricing\nEqualizi
ng Externalities). The framework is sufficiently general to be\ncombined w
ith any optimization algorithm that is based on local\nsearch.\n\nIn the t
alk I'll outline the algorithm\, and open problem/research\ndirections tha
t it raises.\n\nAs an application of the framework\, I will discuss a spec
ial case of\napplying the framework to the problem of one-sided allocation
with\nlotteries. In this case\, we obtain a strengthening of the 1979 res
ult\nby Hylland and Zeckhauser on allocation via a competitive equilibrium
\nfrom equal incomes (CEEI). The [HZ79] result posits that there is a\n(fr
actional) allocation and a set of item prices such that the\nallocation is
a competitive equilibrium given prices. We further show\nthat there is al
ways a reweighing of the players' utility values such\nthat running the st
andard unit-demand VCG with reweighed utilities\nleads to a HZ-equilibrium
prices. Interestingly\, not all HZ\ncompetitive equilibria come from VCG
prices.
DTSTART:20221212T161500Z
DTEND:20221212T171500Z
LAST-MODIFIED:20230120T183529Z
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-525
END:VEVENT
BEGIN:VEVENT
UID:38306431-3739-4431-b731-623836356263
DTSTAMP:20230209T063950Z
CREATED:20220808T192106Z
DESCRIPTION:Topic: A Characterization of Multiclass Learnability\n\nSpeaker
s: Nataly Brukhim\n\nAffiliation: Princeton University\n\nA seminal result
in learning theory characterizes the PAC learnability\nof binary classes
through the VC dimension. Extending this\ncharacterization to the general
multiclass setting has been open since\nthe late 1980s.\n\nWe resolve this
problem by characterizing multiclass PAC learnability\nthrough the DS dim
ension\, a combinatorial dimension defined by Daniely\nand Shalev-Shwartz
(2014).\n\nThe classical characterization of the binary case boils down to
\nempirical risk minimization. In contrast\, our characterization of the\n
multiclass case involves a variety of algorithmic ideas\; these include\na
natural setting we call list PAC learning. In the list learning\nsetting\
, instead of predicting the label of a given unseen input\, the\ngoal is t
o provide a short list of labels which contains the correct\none with high
probability.\n\nOur second main result concerns the Natarajan dimension\,
which has\nbeen a central candidate for characterizing multiclass learnab
ility.\nThis dimension was introduced by Natarajan (1988) as a barrier for
PAC\nlearning. Whether the Natarajan dimension characterizes PAC\nlearnab
ility in general has been posed as an open question in several\npapers sin
ce. We provide a negative answer: we construct a\nnon-learnable class with
Natarajan dimension one.\n\nFor the construction\, we identify a fundamen
tal connection between\nconcept classes and topology. We crucially rely on
a deep and involved\ngeometric-group-theoretic construction by Januszkiew
icz and\nSwiatkowski. This proof provides another demonstration of the fru
itful\nlinks learning theory has with different areas in mathematics.\n\nJ
oint work with Daniel Carmon\, Irit Dinur\, Shay Moran and Amir\nYehudayof
f.
DTSTART:20221213T153000Z
DTEND:20221213T173000Z
LAST-MODIFIED:20230120T183615Z
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-522
END:VEVENT
BEGIN:VEVENT
UID:31343037-3430-4336-a161-636366346661
DTSTAMP:20230209T063950Z
CREATED:20221209T181240Z
DESCRIPTION:Topic: Non-measurability of the inverse theorem for the Gowers
norms\n\nSpeakers: Terence Tao\n\nAffiliation: Member\, School of Mathemat
ics\n\nOver a high-dimensional vector space $F_p^n $over a fixed finite fi
eld\n$F_p$\, the inverse theorem for the Gowers norm asserts that a bounde
d\nfunction f on this space that has a large Gowers $U^{k+1}$ norm\, must
\nnecessarily correlate with a phase polynomial e(P) of degree $k$ this\nr
esult has a number of applications in additive combinatorics and\nproperty
testing. In the high-characteristic case $p >= k-1$ it is\nknown that th
is phase polynomial e(P) is 'measurable' in the sense\nthat it can be appr
oximated to high accuracy by a function of a\nbounded number of random shi
fts of $f$. In joint work with Asgar\nJamneshan and Or Shalom\, we show t
hat this measurability fails when\np=2 and k=5\, thus functions of large $
U^6(F_2^n)$ norm correlate with\nquintic phases\, but such phases can be n
ecessarily non-measurable.\n\n
DTSTART:20230123T161500Z
DTEND:20230123T171500Z
LAST-MODIFIED:20230201T204457Z
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-529
END:VEVENT
BEGIN:VEVENT
UID:36303163-6432-4530-a365-626461623166
DTSTAMP:20230209T063950Z
CREATED:20221209T182451Z
DESCRIPTION:Topic: Locally Decodable Codes\n\nSpeakers: Zeev Dvir\n\nAffili
ation: Princeton University\n\nA Locally Decodable Codes (LDC) is an error
correcting code which\nallows the decoding of a single message symbol fro
m a few queries to a\npossibly corrupted encoding. LDCs can be constructe
d\, for example\,\nfrom low degree polynomials over a finite field (with l
ocal decoding\nalong a random line) and also using set systems with restr
icted\nmodular intersections (Matching-Vector codes). Despite the wide\nr
ange of applications in mathematics and theoretical computer science\,\nth
ere are still big gaps in our understanding of LDCs. In particular\,\nwe s
till don't know if there exist LDCs with polynomial encoding\nlength and
constant locallity (even non-explicitly). In this talk I\nwill survey the
known lower and upper bounds on LDCs and outline the\nmain open problems.
We will focus on the linear algebraic (as opposed\nto information theoret
ic) view of LDCs\, allowing for an arbitrary\nunderlying field. This view
leads to problem statements which are\nreminiscent of more traditional li
ne/point incidence problems.
DTSTART:20230124T153000Z
DTEND:20230124T173000Z
LAST-MODIFIED:20230201T204537Z
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-524
END:VEVENT
BEGIN:VEVENT
UID:62653534-3336-4137-b464-653466643030
DTSTAMP:20230209T063950Z
CREATED:20221209T181412Z
DESCRIPTION:Topic: On Matrix Multiplication and Polynomial Identity Testing
\n\nSpeakers: Robert Andrews\n\nAffiliation: University of Illinois Urbana
-Champaign\n\nDetermining the complexity of matrix multiplication is a fun
damental\nproblem of theoretical computer science. It is popularly conject
ured\nthat matrices can be multiplied in nearly-linear time. If true\, thi
s\nconjecture would yield similarly-fast algorithms for a wide array of\np
roblems in linear algebra and beyond. However\, if such near-linear\ntime
algorithms for matrix multiplication do not exist\, is it possible\nto lev
erage the hardness of multiplying matrices to design algorithms\nfor other
problems? In this talk\, I will describe how lower bounds on\nthe complex
ity of matrix multiplication can be used to design a faster\ndeterministic
algorithm to test if two polynomials\, encoded as\nalgebraic circuits\, a
re equal.
DTSTART:20230130T161500Z
DTEND:20230130T171500Z
LAST-MODIFIED:20230201T204722Z
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-530
END:VEVENT
BEGIN:VEVENT
UID:37616166-3231-4337-b430-373333333736
DTSTAMP:20230209T063950Z
CREATED:20221209T183050Z
DESCRIPTION:Topic: A Subpolynomial Approximation Algorithm for Graph Crossi
ng Number in Low-Degree Graphs\n\nSpeakers: Zihan Tan\n\nAffiliation: Rutg
ers University\n\nGraph Crossing Number is a fundamental and extensively s
tudied problem\nwith wide ranging applications. In this problem\, the goal
is to draw\nan input graph $G$ in the plane so as to minimize the number
of\ncrossings between the images of its edges. The problem is notoriously
\ndifficult\, and despite extensive work\, non-trivial approximation\nalgo
rithms are only known for bounded-degree graphs. Even for this\nspecial ca
se\, the best current algorithm achieves a $\tilde\nO(\sqrt{n})$-approxima
tion\, while the best current negative results do\nnot rule out constant-f
actor approximation. All current approximation\nalgorithms for the problem
build on the same paradigm\, which is also\nused in practice: compute a s
et $E'$ of edges (called a planarizing\nset) such that $G\setminus E'$ is
planar\; compute a planar drawing of\n$G\setminus E'$\; then add the drawi
ngs of the edges of E to the\nresulting drawing. Unfortunately\, there are
examples of graphs $G$\, in\nwhich any implementation of this method must
incur $\Omega(OPT^2)$\ncrossings\, where OPT is the value of the optimal
solution. This\nbarrier seems to doom the only currently known approach to
designing\napproximation algorithms for the problem\, and to prevent it f
rom\nyielding a better than $\tilde O(\sqrt{n})$-approximation.\n\nWe prop
ose a new paradigm that allows us to overcome this barrier.\nUsing the new
paradigm\, we reduce the Crossing Number problem to\nCrossing Number with
Rotation System – a variant of the Crossing\nNumber problem\, in which th
e ordering of the edges incident to every\nvertex is fixed as part of inpu
t. We then show a randomized algorithm\nfor this new problem\, that allows
us to obtain a subpolynomial\napproximation for Graph Crossing Number on
low-degree graphs.\n\nThis talk is based on joint work with Julia Chuzhoy
and Sepideh\nMahabadi.
DTSTART:20230131T153000Z
DTEND:20230131T173000Z
LAST-MODIFIED:20230201T204752Z
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-525
END:VEVENT
BEGIN:VEVENT
UID:37396638-3566-4466-a138-303435633638
DTSTAMP:20230209T063950Z
CREATED:20221209T181441Z
DESCRIPTION:Topic: Smooth Coverings of Space\n\nSpeakers: Oded Regev\n\nAff
iliation: New York University\n\nLet K be a convex body in $R^n$. In some
cases (say when K is a cube)\,\nwe can tile $R^n$ using translates of K. H
owever\, in general (say when\nK is a ball) this is impossible. Neverthele
ss\, we show that one can\nalways cover space 'smoothly' using translates
of K\, in the sense\nthat *each* point in $R^n$ is covered by almost the s
ame small number\nof translates of K (specifically\, (1+-eps)poly(n)). Mor
eover\, we show\nthat this can be achieved by taking the translates to be
the set of\npoints in a random lattice. These results represent substantia
l\nimprovements to bounds of Rogers from the 1950s. The key to the proof\n
are recent breakthroughs due to Dvir\, Dhar\, and others regarding the\ndi
screte Kakeya problem. I will present some history\, applications in\nengi
neering and computer science\, and ideas of the proofs. No\nprerequisites
beyond undergraduate material (measures\, volumes\, vector\nspaces over fi
nite fields) will be assumed.\n\nBased on joint work with Or Ordentlich an
d Barak Weiss (one paper\npublished in J. AMS 2022 https://arxiv.org/abs/2
006.00340 and another\nin progress)
DTSTART:20230206T161500Z
DTEND:20230206T171500Z
LAST-MODIFIED:20230206T201658Z
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-531
END:VEVENT
BEGIN:VEVENT
UID:31356265-3836-4464-b463-643432663263
DTSTAMP:20230209T063950Z
CREATED:20221209T183114Z
DESCRIPTION:Topic: Overview and Recent Results in Combinatorial Auctions\n
\nSpeakers: Matt Weinberg\n\nAffiliation: Princeton University\n\nIn this
talk\, I'll first give a broad overview of the history of\ncombinatorial a
uctions within TCS\, and then discuss some recent\nresults.\n\nCombinatori
al auctions center around the following problem: There is a\nset M of m it
ems\, and N of n bidders. Each bidder i has a valuation\nfunction $v_i$ fr
om subsets of M to real numbers. The goal is to\npartition the items into
$S_1\,\ldots$\, $S_n$ maximizing $\sum_i\nv_i(S_i)$.\n\nI'll cover 2x2 var
iants of this problem:\n\n * Computational model (brief overview and state
ments of results): n\nparties each separately hold one of the $v_i$\, and
they must use\npoly(n\,m) runtime/queries/etc. to find as good an approxim
ation as\npossible.\n * vs. Communication model (main focus): n parties ea
ch separately\nhold one of the $v_i$ and they must use poly(n\,m) communic
ation to\nfind as good an approximation as possible.\n * Algorithm Design
version (one main focus): all parties honestly\nparticipate in whatever pr
otocol is proposed.\n * Mechanism Design version (also a main focus): The
designer is\nallowed to charge price $p_i$ to agent i\, if desired. Party
i will\nbehave in whatever way they believe maximizes $v_i(S_i) - p_i$. \n
\nA sample of results I'll aim to discuss (at varying levels of detail):\n
\n * Tight bounds on achievable approximation guarantees for\nalgorithms.
\n * The Vickrey-Clarke-Groves auction: a black-box reduction from\nexact
mechanism design to exact algorithm design.\n * Maximal-in-range auctions:
tight bounds on the approximation\nguarantees achievable by 'VCG-like' id
eas.\n * Separations between approximation guarantees achievable by\nalgor
ithms vs. mechanisms.\n\nNo prior background in game theory or combinatori
al auctions will be\nassumed.
DTSTART:20230207T153000Z
DTEND:20230207T173000Z
LAST-MODIFIED:20230207T144945Z
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-526
END:VEVENT
BEGIN:VEVENT
UID:64323534-3031-4438-b664-363831323265
DTSTAMP:20230209T063950Z
CREATED:20221209T181515Z
DESCRIPTION:Topic: Efficient Verification of Computation on Untrusted Platf
orms\n\nSpeakers: Yael Kalai\n\nAffiliation: Massachusetts Institute of Te
chnology/Microsoft\n\nEfficient verification of computation is fundamental
to computer\nscience and is at the heart of the P vs. NP question. Recent
ly it\nhas had growing practical significance\, especially with\nthe incre
asing popularity of blockchain technologies and cloud\ncomputing. In this
talk\, I will present schemes for verifying the\ncorrectness of a computat
ion. I will discuss their impact\, both\non cryptography and on theory of
computation at large\, as well as\ntheir impact on practice.
DTSTART:20230213T161500Z
DTEND:20230213T171500Z
LAST-MODIFIED:20230131T182002Z
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-532
END:VEVENT
BEGIN:VEVENT
UID:66386633-6262-4935-b937-393139396266
DTSTAMP:20230209T063950Z
CREATED:20221209T183148Z
DESCRIPTION:Topic: Rainbow Matchings in Hypergraphs\n\nSpeakers: Cosmin Poh
oata\n\nAffiliation: Member\, School of Mathematics\n\nSuppose we are give
n matchings $M_1\,....\,M_N$ of size t in some\nr-uniform hypergraph\, and
let us think of each matching having a\ndifferent color. How large does N
need to be (in terms of t and r)\nsuch that we can always find a rainbow
matching of size t? This\nproblem was first introduced by Aharoni and Berg
er\, and has since been\nstudied by several different authors. While inter
esting for its own\nsake in the context of finding transversals in Latin S
quares (e.g. the\nRyser–Brualdi–Stein Conjecture)\, it is perhaps not too
surprising\nthat this question is also connected with different sides of a
dditive\ncombinatorics. In this talk\, we will survey some of these connec
tions\,\ndiscuss some recent results that more or less completely answer t
he\noriginal question when one of the parameters t or r is fixed\, and the
n\nend with some (fairly arbitrary) speculations/open problems.\n\nJoint w
ork with Lisa Sauermann and Dmitrii Zakharov. \n\n
DTSTART:20230214T153000Z
DTEND:20230214T173000Z
LAST-MODIFIED:20230207T132043Z
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-527
END:VEVENT
BEGIN:VEVENT
UID:36643637-3134-4936-b265-393835333131
DTSTAMP:20230209T063950Z
CREATED:20221209T181606Z
DESCRIPTION:Topic: Induced Subgraphs and Tree Decompositions\n\nSpeakers: M
aria Chudnovsky\n\nAffiliation: Princeton University\n\nTree decomposition
s are a powerful tool in both structural graph\ntheory and graph algorithm
s. Many hard problems become tractable if\nthe input graph is known to hav
e a tree decomposition of bounded\n“width”. Exhibiting a particular kind o
f a tree decomposition is\nalso a useful way to describe the structure of
a graph.\n\nTree decompositions have traditionally been used in the contex
t of\nforbidden graph minors\; bringing them into the realm of forbidden\n
induced subgraphs has until recently remained out of reach. Over the\nlast
couple of years we have made significant progress in this\ndirection\, ex
ploring both the classical notion of bounded tree-width\,\nand concepts of
more structural flavor. This talk will survey some of\nthese ideas and re
sults.
DTSTART:20230220T161500Z
DTEND:20230220T171500Z
LAST-MODIFIED:20230123T152432Z
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-533
END:VEVENT
BEGIN:VEVENT
UID:30303136-3530-4738-a465-633263353661
DTSTAMP:20230209T063950Z
CREATED:20221216T202601Z
DESCRIPTION:Speakers: Matija Bucic\n\nAffiliation: Veblen Research Instruct
or\, School of Mathematics
DTSTART:20230221T153000Z
DTEND:20230221T173000Z
LAST-MODIFIED:20230203T205045Z
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-535
END:VEVENT
BEGIN:VEVENT
UID:32323564-3736-4332-a162-396466353333
DTSTAMP:20230209T063950Z
CREATED:20221209T181630Z
DESCRIPTION:Topic: Two (More) Algorithms for Set Cover \n\nSpeakers: Anupam
Gupta\n\nAffiliation: Carnegie Mellon University\n\nIn the minimum cost s
et cover problem\, a set system is given as\ninput\, and the goal is to fi
nd a collection of sets with minimum cost\nwhose union covers the universe
. This NP-hard problem has long been\nknown to admit logarithmic approxima
tions. Moreover\, the logarithmic\nguarantee is tight\, unless P=NP. In th
is talk I will present two new\napproaches to get similar guarantees\, whi
ch arose from trying to get\nrefined guarantees for the problem in beyond-
worst-case settings. \n\nThe talk is based on joint works with Greg Kehne
(CMU and Harvard)\,\nEuiwoong Lee (U. Michigan)\, Roie Levin (CMU and Tel
Aviv U)\, and Jason\nLi (CMU and Simons/Berkeley).
DTSTART:20230306T161500Z
DTEND:20230306T171500Z
LAST-MODIFIED:20230208T135024Z
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-534
END:VEVENT
BEGIN:VEVENT
UID:38353338-6231-4535-a237-323165353930
DTSTAMP:20230209T063950Z
CREATED:20221209T183341Z
DESCRIPTION:Topic: Recent Progress in Randomness Extraction\n\nSpeakers: Es
han Chattopadhyay\n\nAffiliation: Cornell University\n\nRandomness is a vi
tal resource in computation\, with many applications\nin areas such as cry
ptography\, data-structures and algorithm design\,\nsampling\, distributed
computing\, etc. However generating truly random\nbits is expensive\, and
most sources in nature produce correlated bits.\nA randomness extractor i
s informally defined to be an algorithm that\ncan purify such defective so
urces of randomness to output purely\nrandom bits.\n\nThe area of randomne
ss extraction has a long and rich history of\nstudying various models of d
efective sources\, and this line of\ninvestigation has uncovered various i
nteresting connections to\nmathematics as well as other areas within theo
retical computer\nscience. Recently\, this area has seen exciting progres
s on many\nlongstanding open problems\, which have also led to progress\no
n related questions in extremal combinatorics (such as explicit\nconstruct
ions of Ramsey graphs). In this talk\, I will survey these\nresults and th
e new techniques that have led to this progress. I will\nalso discuss open
questions that seem within reach.\n\nNo prior background in randomness ex
traction will be assumed for this\ntalk.
DTSTART:20230307T153000Z
DTEND:20230307T173000Z
LAST-MODIFIED:20230207T194121Z
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-528
END:VEVENT
BEGIN:VEVENT
UID:66613738-3636-4933-b966-363765353337
DTSTAMP:20230209T063950Z
CREATED:20221209T181755Z
DESCRIPTION:Speakers: Chinmay Nirkhe\n\nAffiliation: IBM Quantum
DTSTART:20230313T151500Z
DTEND:20230313T161500Z
LAST-MODIFIED:20230208T164023Z
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-535
END:VEVENT
BEGIN:VEVENT
UID:37386439-3936-4532-b966-653762353535
DTSTAMP:20230209T063950Z
CREATED:20221209T183422Z
DESCRIPTION:
DTSTART:20230314T143000Z
DTEND:20230314T163000Z
LAST-MODIFIED:20221209T183535Z
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-531
END:VEVENT
BEGIN:VEVENT
UID:38663235-3536-4661-a531-343838383436
DTSTAMP:20230209T063950Z
CREATED:20221209T181839Z
DESCRIPTION:Speakers: Mathias Schacht\n\nAffiliation: Universität Hamburg
DTSTART:20230320T151500Z
DTEND:20230320T161500Z
LAST-MODIFIED:20230105T135613Z
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-536
END:VEVENT
BEGIN:VEVENT
UID:38303332-3937-4239-b534-663633666334
DTSTAMP:20230209T063950Z
CREATED:20221209T183442Z
DESCRIPTION:
DTSTART:20230321T143000Z
DTEND:20230321T163000Z
LAST-MODIFIED:20221209T183508Z
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-530
END:VEVENT
BEGIN:VEVENT
UID:34376261-3332-4538-a437-383563626538
DTSTAMP:20230209T063950Z
CREATED:20221209T183624Z
DESCRIPTION:Speakers: Dor Yosef Minzer\n\nAffiliation: Massachusetts Instit
ute of Technology
DTSTART:20230328T143000Z
DTEND:20230328T163000Z
LAST-MODIFIED:20230105T135733Z
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-532
END:VEVENT
BEGIN:VEVENT
UID:36653434-6232-4665-b661-613565383232
DTSTAMP:20230209T063950Z
CREATED:20221209T181907Z
DESCRIPTION:Speakers: Nina Kamčev\n\nAffiliation: University of Zagreb
DTSTART:20230403T151500Z
DTEND:20230403T161500Z
LAST-MODIFIED:20230124T202341Z
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-537
END:VEVENT
BEGIN:VEVENT
UID:38373865-3833-4631-b837-333238626366
DTSTAMP:20230209T063950Z
CREATED:20221209T183650Z
DESCRIPTION:
DTSTART:20230404T143000Z
DTEND:20230404T163000Z
LAST-MODIFIED:20221209T183706Z
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-533
END:VEVENT
BEGIN:VEVENT
UID:36623361-3766-4632-b031-326536626132
DTSTAMP:20230209T063950Z
CREATED:20221209T182100Z
DESCRIPTION:
DTSTART:20230410T151500Z
DTEND:20230410T161500Z
LAST-MODIFIED:20221209T182126Z
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-538
END:VEVENT
BEGIN:VEVENT
UID:37386133-3339-4665-b532-663764306564
DTSTAMP:20230209T063950Z
CREATED:20221209T183715Z
DESCRIPTION:Speakers: Assaf Naor\n\nAffiliation: Princeton University
DTSTART:20230411T143000Z
DTEND:20230411T163000Z
LAST-MODIFIED:20230105T140004Z
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-534
END:VEVENT
BEGIN:VEVENT
UID:63383738-3937-4032-b334-343266653839
DTSTAMP:20230209T063950Z
CREATED:20230105T142917Z
DESCRIPTION:Speakers: Noga Alon\n\nAffiliation: Princeton University
DTSTART:20230417T151500Z
DTEND:20230417T161500Z
LAST-MODIFIED:20230105T142948Z
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-541
END:VEVENT
BEGIN:VEVENT
UID:38373962-3639-4466-b232-393833343438
DTSTAMP:20230209T063950Z
CREATED:20230105T142617Z
DESCRIPTION:
DTSTART:20230418T143000Z
DTEND:20230418T163000Z
LAST-MODIFIED:20230105T142713Z
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-536
END:VEVENT
BEGIN:VEVENT
UID:30306133-3432-4339-a665-653965663933
DTSTAMP:20230209T063950Z
CREATED:20230105T143018Z
DESCRIPTION:
DTSTART:20230424T151500Z
DTEND:20230424T161500Z
LAST-MODIFIED:20230105T143037Z
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-542
END:VEVENT
BEGIN:VEVENT
UID:65393634-6364-4138-b963-386438303139
DTSTAMP:20230209T063950Z
CREATED:20230105T142741Z
DESCRIPTION:Speakers: Nikhil Bansal\n\nAffiliation: University of Michigan
DTSTART:20230425T143000Z
DTEND:20230425T163000Z
LAST-MODIFIED:20230125T133049Z
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-537
END:VEVENT
END:VCALENDAR