BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//85f20b73fecb3e0e6ca434791a2aea4a.ias.edu//NONSGML kigkonsult.se iCalcreator 2.41.76//
CALSCALE:GREGORIAN
UID:66383637-6565-4135-a133-636266643061
X-WR-TIMEZONE:UTC
X-WR-CALNAME:IAS CSDM Seminars
BEGIN:VEVENT
UID:64663339-6330-4565-b465-616435386431
DTSTAMP:20230530T051157Z
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:20230321T143803Z
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:66386638-3535-4561-b933-333339643334
DTSTAMP:20230530T051157Z
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:20230321T143833Z
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:64346431-3433-4634-b339-316136616565
DTSTAMP:20230530T051157Z
CREATED:20221209T181755Z
DESCRIPTION:Topic: Why Can’t We Classically Describe Quantum Systems?\n\nSp
eakers: Chinmay Nirkhe\n\nAffiliation: MIT-IBM Watson AI Lab\n\nA central
goal of physics is to understand the low-energy solutions of\nquantum inte
ractions between particles. This talk will focus on the\ncomplexity of _de
scribing_ low-energy solutions\; I will show that we\ncan construct quantu
m systems for which the low-energy solutions are\nhighly complex and unlik
ely to exhibit succinct classical\ndescriptions. I will discuss the implic
ations these results have for\nrobust entanglement at constant temperature
and the quantum PCP\nconjecture. En route\, I will discuss our positive r
esolution of the No\nLow-energy Trivial States (NLTS) conjecture on the ex
istence of robust\ncomplex entanglement.\n\nMathematically\, for an _n-_pa
rticle system\, the low-energy states are\nthe eigenvectors corresponding
to small eigenvalues of an\nexp(_n_)-sized matrix called the Hamiltonian\,
which describes the\ninteractions between the particles. Low-energy state
s are the quantum\ngeneralizations of approximate solutions to satisfiabil
ity problems\nsuch as 3-SAT. In this talk\, I will discuss the theoretical
computer\nscience techniques used to prove circuit lower bounds for all\n
low-energy states. This morally demonstrates the existence of\nHamiltonian
systems whose entire low-energy subspace is robustly\nentangled.
DTSTART:20230313T151500Z
DTEND:20230313T161500Z
LAST-MODIFIED:20230321T143900Z
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:35323763-3739-4430-a565-636137353662
DTSTAMP:20230530T051157Z
CREATED:20230310T184529Z
DESCRIPTION:Topic: Strong Bounds for 3-Progressions\n\nSpeakers: Raghu Meka
\, Zander Kelley\n\nAffiliation: University of California\, Los Angeles\;
University of Illinois Urbana-Champaign\n\nSuppose you have a set _S_ of i
ntegers from _{1 \, 2 \, … \,\nN}_ that contains at least _N / C_ elements
. Then for large\nenough _N_ \, must _S_ contain three equally spaced numb
ers (i.e.\,\na 3-term arithmetic progression)?\n\nIn 1953\, Roth showed th
at this is indeed the case when _C ≈ (log\n____ log ____ N)_\, while Beh
rend in 1946 showed that _C_ can\nbe at most _2 Ω(√log ____N__)_. Since t
hen\, the problem has\nbeen a cornerstone of the area of additive combinat
orics. Following a\nseries of remarkable results\, a celebrated paper from
2020 due to\nBloom and Sisask improved the lower bound on _C_ to _C = (lo
g\nN) (1 + c)_\, for some constant _c > 0_.\n\nThis talk will describe a n
ew work showing that the same holds\nwhen _C ≈ 2(log ____ N)0.09_\, thus
getting closer to Behrend's\nconstruction.\n\nBased on joint work with Zan
der Kelley.
DTSTART:20230320T140000Z
DTEND:20230320T150000Z
LAST-MODIFIED:20230322T172233Z
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-544
END:VEVENT
BEGIN:VEVENT
UID:39623562-6335-4433-b437-626638616438
DTSTAMP:20230530T051157Z
CREATED:20221209T181839Z
DESCRIPTION:Topic: Extremal Problems for Uniformly Dense Hypergraphs\n\nSpe
akers: Mathias Schacht\n\nAffiliation: Universität Hamburg\n\nExtremal com
binatorics is a central research area in discrete\nmathematics. The field
can be traced back to the work of Turán and it\nwas established by Erdős t
hrough his fundamental contributions and\nhis uncounted guiding questions.
Since then it has grown into an\nimportant discipline with strong ties to
other mathematical areas such\nas theoretical computer science\, number t
heory\, and ergodic theory.\n\nWe focus on extremal problems for hypergrap
hs\, which were introduced\nby Turán. After solving the analogous question
for graphs\, Turán\nasked to determine the maximum cardinality of a set E
of 3-element\nsubsets of a given n-element set V such that for any 4 elem
ents of V\nat least one triple is missing in E. This innocent looking prob
lem is\nstill open and despite a great deal of effort over the last 80 yea
rs\nand our knowledge is still somewhat limited. We consider a variant\no
f the problem by imposing additional restrictions on the distribution\nof
the 3-element subsets in E. These additional assumptions yield a\nfiner co
ntrol over the corresponding extremal problem. In fact\, this\nleads to ma
ny interesting and more manageable subproblems\, some of\nwhich were alrea
dy considered by Erdős and Sós in the 1980ies. The\nadditional assumptions
on the distribution of the 3-element subsets\nare closely related to the
theory of quasirandom discrete structures\,\nwhich was pioneered by Szemer
édi and became a central theme in the\nfield. In fact\, the hypergraph ext
ensions by Gowers and by Rödl et\nal. of the regularity lemma provide esse
ntial tools for this line of\nresearch.
DTSTART:20230320T151500Z
DTEND:20230320T161500Z
LAST-MODIFIED:20230322T172207Z
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:65323230-6365-4766-a134-373464333834
DTSTAMP:20230530T051157Z
CREATED:20221209T183442Z
DESCRIPTION:Topic: Strong Bounds for 3-Progressions: In-Depth\n\nSpeakers:
Raghu Meka\, Zander Kelley\n\nAffiliation: University of California\, Los
Angeles\; University of Illinois Urbana-Champaign\n\nSuppose you have a se
t A of integers from {1\, 2\, …\, N} that contains\nat least N / C element
s. Then for large enough N\, must A contain\nthree equally spaced numbers
(i.e.\, a 3-term arithmetic\nprogression)? \n\nIn 1953\, Roth showed that
this is indeed the case when C ≈ log \nlog N\, while Behrend in 1946 s
howed that C can be at most\n2^√log(N) by giving an explicit construction
of a large set with no\n3-term progressions. Since then\, the problem has
been a cornerstone\nof the area of additive combinatorics. Following a s
eries of\nremarkable results\, a celebrated paper from 2020 due to Bloom a
nd\nSisask improved the lower bound on C to C = (log N)^(1 + c)\, for some
\nconstant c > 0.\n\nIn a recent new work with Raghu Meka\, it was shown t
hat the same holds\nwhen C ≈ 2^(log N)^(0.09)\, thus getting closer to B
ehrend's\nconstruction. In this talk we give an in-depth look at the proo
f.
DTSTART:20230321T143000Z
DTEND:20230321T163000Z
LAST-MODIFIED:20230322T172139Z
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:63306532-3433-4139-b264-353065643763
DTSTAMP:20230530T051157Z
CREATED:20221209T183624Z
DESCRIPTION:Topic: The Lens of Abelian Embeddings\n\nSpeakers: Dor Minzer\n
\nAffiliation: Massachusetts Institute of Technology\n\nA predicate $P:\Si
gma^k \to {0\,1}$ is said to be linearly embeddable\nif the set of assignm
ents satisfying it can be embedded in an Abelian\ngroup. \n\nIn this talk\
, we will present this notion and mention problems it\nrelates to from var
ious areas. These areas include hardness of\napproximation\, multi-player
parallel repetition\, property testing and\nadditive combinatorics. Depend
ing on time\, we will discuss a few\npartial results on the study of this
notion\, as well as applications.\n\nMostly based on joint works with Amey
Bhangale\, Subhash Khot.
DTSTART:20230328T143000Z
DTEND:20230328T163000Z
LAST-MODIFIED:20230404T131934Z
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:36316135-6332-4265-b536-386531313833
DTSTAMP:20230530T051157Z
CREATED:20221209T181907Z
DESCRIPTION:Topic: Common Linear Patterns Are Rare\n\nSpeakers: Nina Kamčev
\n\nAffiliation: University of Zagreb\n\nSeveral classical results in Rams
ey theory (including famous theorems\nof Schur\, van der Waerden\, Rado) d
eal with finding monochromatic\nlinear patterns in two-colourings of the i
ntegers. Our topic will be\nquantitative extensions of such results. A l
inear system $L$ over\n$\mathbb{F}_q$ is _common_ if the number of monochr
omatic solutions\nto $L=0$ in any two-colouring of $\mathbb{F}_q^n$ is asy
mptotically at\nleast the expected number of monochromatic solutions in a
random\ntwo-colouring of $\mathbb{F}_q^n$. Motivated by existing results
for\nspecific systems (such as Schur triples and arithmetic progressions)\
,\nas well as extensive research on common and Sidorenko graphs\, the\nsys
tematic study of common systems of linear equations was recently\ninitiate
d by Saad and Wolf. Fox\, Pham and Zhao characterised common\nlinear equat
ions.\n\nI will talk about recent progress towards a classification of com
mon\nsystems of two or more linear equations. In particular\, any system
\ncontaining a four-term arithmetic progression is uncommon. This\nfollow
s from a more general result which allows us to deduce the\nuncommonness o
f a general system from certain properties of one- or\ntwo-equation subsys
tems.\n\nJoint work with Anita Liebenau and Natasha Morrison.
DTSTART:20230403T151500Z
DTEND:20230403T161500Z
LAST-MODIFIED:20230404T132003Z
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:62663232-3031-4162-b164-306563383432
DTSTAMP:20230530T051157Z
CREATED:20221209T183650Z
DESCRIPTION:Topic: Hausdorff Dimension Analogues of the Elekes - Ronyai The
orem and Related Problems\n\nSpeakers: Orit Raz\n\nAffiliation: Hebrew Uni
versity\; Visitor\, School of Mathematics\n\nIf $f$ is a real polynomial a
nd $A$ and $B$ are finite sets of\ncardinality $n$\, then Elekes and Ronya
i proved that either $f(A\times\nB)$ is much larger than $n$\, or $f$ has
a very specific form\n(essentially\, $f(x\,y)=x+y$). In the talk I will te
ll about an analogue\nof this problem\, where $A$ and $B$ are now infinite
subsets of\n$\mathcal{R}$\, each of Hausdorff dimension $\alpha$. In a re
cent\nresult\, joint with Josh Zahl\, we prove that in this case $f(A\time
s\nB)$ will have Hausdorff dimension at least $\alpha+c$\, where\n$c=c(\al
pha)>0$\, unless $f$ has the specific special form as above. \n\nI will ex
plain a connection between this problem and projection\ntheorems\, in the
spirit of Kaufman\, Bourgain\, and Shmerkin.\nConcretely\, I will tell abo
ut the following result: Given a set E in\nthe plane\, consider the set of
exceptional points\, for which the\npinned distance set $\Delta_p(E)$ has
small Hausdorff dimension\, that\nis\, close to ${\rm dim}(A)/2$. If this
set has a positive dimension\nthen it must have a special structure. As a
corollary one deduces a\ncertain instance of the pinned Falconer’s distan
ce problem.\n\nFor the proofs we apply a reduction to the discretized sett
ing\nintroduced by Katz and Tao. In the discretized setting\, our proofs a
re\ninspired by their counterparts in the finite case\, where the classica
l\nSzemeredi and Trotter incidence bound is replaced by a recent result\no
f Shmerkin. \n\nThe talk is based on a joint work with Josh Zahl.
DTSTART:20230404T143000Z
DTEND:20230404T163000Z
LAST-MODIFIED:20230501T172535Z
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:30643030-6162-4335-b234-396532326266
DTSTAMP:20230530T051157Z
CREATED:20221209T182100Z
DESCRIPTION:Topic: Quantum Error Correction\, Systolic Geometry\, and Proba
bilistic Embeddings\n\nSpeakers: Elia Portnoy\n\nAffiliation: Massachusett
s Institute of Technology\n\nA CSS quantum code $\mathcal{C} = (W_1\, W_2)
$ is a pair of orthogonal\nsubspaces in $\mathbb{F}_2^n$. The distance of
$\mathcal{C}$ is the\nsmallest hamming weight of a vector in $W_1^{\perp}-
W_2$ or\n$W_2^{\perp}-W_1$. A large distance roughly means that the quantu
m\ncode can correct many errors that affect the information stored in\nit.
\n\nIn this talk we show how to construct a CSS quantum code that can\nb
e implemented in a 3-dimensional lattice and has near optimal\ndistance. A
long the way we will discuss a connection between\nquantum codes and systo
lic geometry made by Freedman and Hastings\, as\nwell as a probabilistic e
mbedding result of Gromov and Guth.
DTSTART:20230410T151500Z
DTEND:20230410T161500Z
LAST-MODIFIED:20230501T172611Z
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:33653133-6465-4164-b466-383230383534
DTSTAMP:20230530T051157Z
CREATED:20221209T183715Z
DESCRIPTION:Topic: Updates on the Lipschitz Extension Problem\n\nSpeakers:
Assaf Naor\n\nAffiliation: Princeton University\n\nThe Lipschitz extension
problem is the following basic “meta\nquestion” in metric geometry: Supp
ose that X and Y are metric\nspaces and A is a subset of X. What is the sm
allest K such that every\nLipschitz function f:A\to Y has an extension F:X
\to Y whose Lipschitz\nconstant is at most K times the Lipschitz constant
of f. Such\nextension phenomena are rare\, but when they are available the
y are\nuseful for various applications\, ranging from pure mathematics to
\napproximation theory and algorithms. The Lipschitz extension problem\nha
s attracted the efforts of many mathematicians over the past\ncentury\, an
d the known results introduced a variety of valuable ideas.\nIn this talk
we will explain some of the main achievements\, ideas\,\nchallenges and m
ysteries in this direction\, as well as recent advances\n(both recently pu
blished and forthcoming). Among the topics that we\nwill cover are connect
ions to clustering\, dual formulations\, relations\nto reverse isoperimetr
y\, and approximate versions.
DTSTART:20230411T143000Z
DTEND:20230411T163000Z
LAST-MODIFIED:20230501T172649Z
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:63393366-3537-4533-b130-343839303837
DTSTAMP:20230530T051157Z
CREATED:20230105T142917Z
DESCRIPTION:Topic: Unit and Distinct Distances in Typical Norms\n\nSpeakers
: Noga Alon\n\nAffiliation: Princeton University\n\nErdős' unit distance p
roblem and his related distinct distances\nproblem are arguably the best k
nown open problems in discrete\ngeometry. \n\nThey ask for the maximum pos
sible number of unit distances\, and the\nminimum possible number of disti
nct distances\, respectively\,\ndetermined by n points in the Euclidean pl
ane. The same problems for\nnormed spaces other than the Euclidean plane h
ave been raised in the\n1980s by Ulam and Erdős and attracted a lot of att
ention over the\nyears. We give an essentially tight answer to both questi
ons for\nalmost all norms on $R^d$\, in a certain Baire categoric sense.\n
\nThe results settle\, in a strong and somewhat surprising form\, problems
\nand conjectures of Brass\, of Matousek\, and of Brass-Moser-Pach. The\n
proofs combine combinatorial and geometric ideas with tools from\nLinear A
lgebra\, Topology and Algebraic Geometry.\n\nJoint work with Matija Bucic
and Lisa Sauermann.
DTSTART:20230417T151500Z
DTEND:20230417T161500Z
LAST-MODIFIED:20230501T172718Z
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:64323531-3364-4936-b731-326162653761
DTSTAMP:20230530T051157Z
CREATED:20230105T142617Z
DESCRIPTION:Topic: Existence of Subspace Designs \n\nSpeakers: Ashwin Sah\n
\nAffiliation: Massachusetts Institute of Technology\n\nWe prove the exist
ence of subspace designs with any given parameters\,\nprovided that the di
mension of the underlying space is sufficiently\nlarge in terms of the oth
er parameters of the design and satisfies the\nobvious necessary divisibil
ity conditions. This settles an open\nproblem from the 1970s. Moreover\, w
e also obtain an approximate\nformula for the number of such designs.\n\nJ
oint work with Peter Keevash and Mehtaab Sawhney.
DTSTART:20230418T143000Z
DTEND:20230418T163000Z
LAST-MODIFIED:20230501T172749Z
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:39333062-3430-4632-a262-653161386535
DTSTAMP:20230530T051157Z
CREATED:20230105T143018Z
DESCRIPTION:Topic: Approximating Iterated Multiplication of Stochastic Matr
ices in Small Space \n\nSpeakers: Dean Doron\n\nAffiliation: Ben-Gurion Un
iversity of the Negev\n\nMatrix powering\, and more generally iterated mat
rix multiplication\, is\na fundamental linear algebraic primitive with myr
iad applications in\ncomputer science. Of particular interest is the probl
em’s space \ncomplexity as it constitutes the main route towards resolving
the BPL\nvs. L problem.\n\nIn this talk\, we give the first polynomial im
provement over the\nseminal work by Saks and Zhou (1999)\, who gave a dete
rministic\nalgorithm for approximating the product of n stochastic matrice
s of\ndimension w×w in space O(log3/2n+ (log n)1/2·log w). Our algorithm\n
achieves space complexity of O~(log n+ (log n)1/2·log w)\, which\noutperfo
rms [SZ99] whenever n >> w. In particular\, in the regime log n\n> log2w\,
our algorithm runs in nearly-optimal O~(log n) space\,\nimproving upon th
e previous best O(log3/2n).\n\nJoint work with Gil Cohen\, Ori Sberlo\, an
d Amnon Ta-Shma.
DTSTART:20230424T151500Z
DTEND:20230424T161500Z
LAST-MODIFIED:20230501T172822Z
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:35616166-3163-4634-b338-363562363432
DTSTAMP:20230530T051157Z
CREATED:20230105T142741Z
DESCRIPTION:Topic: A Unified Approach to Discrepancy Minimization\n\nSpeake
rs: Nikhil Bansal\n\nAffiliation: University of Michigan\n\nDiscrepancy th
eory provides a powerful approach to improve upon the\nbounds obtained by
a basic application of the probabilistic method. In\nrecent years\, severa
l algorithmic approaches have been developed for\nvarious classical result
s in the area. In this talk\, I will survey\nsome of these ideas and descr
ibe a recent algorithmic approach based\non barrier-based potential funct
ions that recovers several\nstate-of-the-art results in a simple and unifi
ed way.\n\nBased on joint work with Aditi Laddha and Santosh Vempala.
DTSTART:20230425T143000Z
DTEND:20230425T163000Z
LAST-MODIFIED:20230501T172850Z
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
BEGIN:VEVENT
UID:30626437-3962-4431-b833-343637333934
DTSTAMP:20230530T051157Z
CREATED:20230227T150123Z
DESCRIPTION:Topic: A Constant Lower Bound for Frankl's Union-Closed Sets Co
njecture\n\nSpeakers: Justin Gilmer\n\nAffiliation: Google Brain\n\nA fini
te set system is union-closed if for every pair of sets in the\nsystem the
ir union is also in the system. Frankl in 1979 conjectured\nthat for any
such system there exists an element which is contained in\n½ of the sets i
n that system (the only exception being the family\ncontaining just the em
pty set). In this talk\, I will discuss how a\nsimple insight regarding t
he contrapositive of Frankl's conjecture\neventually led to the discovery
of an information theoretic approach\non the problem and a proof of the fi
rst constant lower bound.
DTSTART:20230501T151500Z
DTEND:20230501T161500Z
LAST-MODIFIED:20230501T130653Z
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-543
END:VEVENT
BEGIN:VEVENT
UID:32323339-3964-4761-b361-613138376631
DTSTAMP:20230530T051157Z
CREATED:20230307T142409Z
DESCRIPTION:Topic: Fitting Various Metrics with Minimum Disagreements\n\nSp
eakers: Euiwoong Lee\n\nAffiliation: University of Michigan\n\nLet C be a
class of metric spaces. We consider the following\ncomputational metric em
bedding problem: given a vector x in R^{n\nchoose 2} representing pairwise
distances between n points\, change the\nminimum number of entries of x t
o ensure that the new distances\ncorrespond to a metric in C. Several inst
antiations of this problem\nhave been actively studied in theoretical comp
uter science and machine\nlearning\, including Correlation Clustering (whe
n C is the class of\nuniform metrics) and Metric Violation Distance (when
C is the class of\nall metrics).\n\nWe present a unified framework and imp
roved approximation algorithms\nfor these metric embedding problems. One c
ommon tool is the\napplication of the 'pivot algorithm\,' originally devel
oped for uniform\nmetrics\, to more general metrics. We also use connectio
ns between\nmetric embedding and constraint satisfaction problems\, which
allows us\nto use stronger convex relaxations based on the Sherali-Adams\n
hierarchy.\n\nBased on joint work with Vincent Cohen-Addad\, Chenglin Fan\
, Arnaud de\nMesmay\, and Alantha Newman.\n\n
DTSTART:20230502T143000Z
DTEND:20230502T163000Z
LAST-MODIFIED:20230502T132656Z
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:32636531-3439-4238-b661-306665326636
DTSTAMP:20230530T051157Z
CREATED:20230320T133438Z
DESCRIPTION:Topic: Graph Vertex Expansion\n\nSpeakers: Theo McKenzie\n\nAff
iliation: Harvard University\n\nIn a vertex expanding graph\, every small
subset of vertices neighbors\nmany different vertices. Random graphs are n
ear-optimal vertex\nexpanders\; however\, it has proven difficult to creat
e families of\nDETERMINISTIC near-optimal vertex expanders\, as the connec
tion between\nvertex and spectral expansion is limited. We discuss success
ful\nattempts to create UNIQUE NEIGHBOR expanders (a weak version of verte
x\nexpansion)\, as well as limitations in using common combinatorial\nmeth
ods to create stronger expanders.
DTSTART:20230508T151500Z
DTEND:20230508T161500Z
LAST-MODIFIED:20230508T120202Z
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-545
END:VEVENT
BEGIN:VEVENT
UID:38643436-3830-4434-b565-633233623838
DTSTAMP:20230530T051157Z
CREATED:20230307T142534Z
DESCRIPTION:Topic: Using Expanders for Fast Graph Algorithms\n\nSpeakers: T
hatchaphol Saranurak\n\nAffiliation: University of Michigan\n\nIn the last
few years\, expanders have been used in fast graph\nalgorithms in differe
nt models\, including static\, dynamic\, and\ndistributed algorithms. I wi
ll survey these applications of\nexpanders\, explain the expander-related
tools behind this development\,\nthen give a tutorial on how to construct
some of these tools\, such as\nexpander decomposition.
DTSTART:20230509T143000Z
DTEND:20230509T163000Z
LAST-MODIFIED:20230509T133647Z
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-538
END:VEVENT
END:VCALENDAR