BEGIN:VCALENDAR
VERSION:2.0
PRODID:researchseminars.org
CALSCALE:GREGORIAN
X-WR-CALNAME:researchseminars.org
BEGIN:VEVENT
SUMMARY:Huacheng Yu (Princeton University)
DTSTART;VALUE=DATE-TIME:20200422T170000Z
DTEND;VALUE=DATE-TIME:20200422T180000Z
DTSTAMP;VALUE=DATE-TIME:20201031T035238Z
UID:TCSPlus/1
DESCRIPTION:Title: Nearly Optimal Static Las Vegas Succinct Dictionary\nby
Huacheng Yu (Princeton University) as part of TCS+\n\nAbstract: TBA\n
END:VEVENT
BEGIN:VEVENT
SUMMARY:Sepideh Mahabadi (TTIC)
DTSTART;VALUE=DATE-TIME:20200429T170000Z
DTEND;VALUE=DATE-TIME:20200429T180000Z
DTSTAMP;VALUE=DATE-TIME:20201031T035238Z
UID:TCSPlus/2
DESCRIPTION:Title: Non-Adaptive Adaptive Sampling in Turnstile Streams\nby
Sepideh Mahabadi (TTIC) as part of TCS+\n\nAbstract: TBA\n
END:VEVENT
BEGIN:VEVENT
SUMMARY:Nathan Klein (University of Washington)
DTSTART;VALUE=DATE-TIME:20200506T170000Z
DTEND;VALUE=DATE-TIME:20200506T180000Z
DTSTAMP;VALUE=DATE-TIME:20201031T035238Z
UID:TCSPlus/3
DESCRIPTION:Title: An improved approximation algorithm for TSP in the half
integral case\nby Nathan Klein (University of Washington) as part of TCS+
\n\nAbstract: TBA\n
END:VEVENT
BEGIN:VEVENT
SUMMARY:Mark Bun (Boston University)
DTSTART;VALUE=DATE-TIME:20200520T170000Z
DTEND;VALUE=DATE-TIME:20200520T180000Z
DTSTAMP;VALUE=DATE-TIME:20201031T035238Z
UID:TCSPlus/4
DESCRIPTION:Title: An Equivalence between Private Classification and Onlin
e Predictability\nby Mark Bun (Boston University) as part of TCS+\n\nAbstr
act: TBA\n
END:VEVENT
BEGIN:VEVENT
SUMMARY:Rahul Ilango (MIT)
DTSTART;VALUE=DATE-TIME:20200527T170000Z
DTEND;VALUE=DATE-TIME:20200527T180000Z
DTSTAMP;VALUE=DATE-TIME:20201031T035238Z
UID:TCSPlus/5
DESCRIPTION:Title: Is it (NP) hard to distinguish order from chaos?\nby Ra
hul Ilango (MIT) as part of TCS+\n\n\nAbstract\n"The Minimum Circuit Size
Problem (MCSP) roughly asks what the ""complexity"" of a given string is.
Informally\, one can think of this as determining the degree of ""computat
ional order"" a string has.\n\nIn the past several years\, there has been
a resurgence of interest in MCSP. A series of exciting results have begun
unraveling what looks to be a fascinating story. This story already reveal
s deep connections between MCSP and a growing list of fields\, including c
ryptography\, learning theory\, structural complexity theory\, average-cas
e complexity\, and circuit complexity. As an example\, Santhanam recently
proved a conditional equivalence between the complexity of MCSP and the ex
istence of one-way functions.\n\nThis talk is split into two parts. The fi
rst part is a broad introduction to MCSP\, answering the following questio
ns: What is this problem? Why is it interesting? What do we know so far\,
and where might the story go next? The second part discusses recent joint
work with Bruno Loff and Igor Oliveira showing that the ""multi-output ver
sion"" of MCSP is NP-hard. "\n\nThe Minimum Circuit Size Problem (MCSP) ro
ughly asks what the "complexity" of a given string is. Informally\, one ca
n think of this as determining the degree of "computational order" a strin
g has.\n\nIn the past several years\, there has been a resurgence of inter
est in MCSP. A series of exciting results have begun unraveling what looks
to be a fascinating story. This story already reveals deep connections be
tween MCSP and a growing list of fields\, including cryptography\, learnin
g theory\, structural complexity theory\, average-case complexity\, and ci
rcuit complexity. As an example\, Santhanam recently proved a conditional
equivalence between the complexity of MCSP and the existence of one-way fu
nctions.\n\nThis talk is split into two parts. The first part is a broad i
ntroduction to MCSP\, answering the following questions: What is this prob
lem? Why is it interesting? What do we know so far\, and where might the s
tory go next? The second part discusses recent joint work with Bruno Loff
and Igor Oliveira showing that the "multi-output version" of MCSP is NP-ha
rd.\n
END:VEVENT
BEGIN:VEVENT
SUMMARY:Michael P. Kim (Stanford University)
DTSTART;VALUE=DATE-TIME:20200603T170000Z
DTEND;VALUE=DATE-TIME:20200603T180000Z
DTSTAMP;VALUE=DATE-TIME:20201031T035238Z
UID:TCSPlus/6
DESCRIPTION:Title: Learning from outcomes: evidence-based rankings\nby Mic
hael P. Kim (Stanford University) as part of TCS+\n\nAbstract: TBA\n
END:VEVENT
BEGIN:VEVENT
SUMMARY:Sahil Singla (Princeton University)
DTSTART;VALUE=DATE-TIME:20200513T170000Z
DTEND;VALUE=DATE-TIME:20200513T180000Z
DTSTAMP;VALUE=DATE-TIME:20201031T035238Z
UID:TCSPlus/7
DESCRIPTION:Title: Online vector balancing and geometric discrepancy\nby S
ahil Singla (Princeton University) as part of TCS+\n\nAbstract: TBA\n
END:VEVENT
BEGIN:VEVENT
SUMMARY:Clifford Stein (Coumbia University)
DTSTART;VALUE=DATE-TIME:20200618T170000Z
DTEND;VALUE=DATE-TIME:20200618T180000Z
DTSTAMP;VALUE=DATE-TIME:20201031T035238Z
UID:TCSPlus/8
DESCRIPTION:Title: Parallel approximate undirected shortest paths via low
hop emulators\nby Clifford Stein (Coumbia University) as part of TCS+\n\n\
nAbstract\nAlthough sequential algorithms with (nearly) optimal running ti
me for finding shortest paths in undirected graphs with non-negative edge
weights have been known for several decades\, near-optimal parallel algori
thms have turned out to be a much tougher challenge. In this talk\, we pre
sent a $(1+\\varepsilon)$-approximate parallel algorithm for computing sho
rtest paths in undirected graphs\, achieving polylog depth and near-linear
work. All prior $(1+\\varepsilon)$-algorithms with polylog depth perform
at least superlinear work. Improving this long-standing upper bound obtai
ned by Cohen (STOC'94) has been open for 25 years.\n\nOur algorithm uses s
everal new tools. Prior work uses hopsets to introduce shortcuts in the gr
aph. We introduce a new notion that we call low hop emulators. We also in
troduce compressible preconditioners\, which we use in conjunction with Se
rman's framework (SODA '17) for the uncapacitated minimum cost flow proble
m.\n\nJoint work with Alex Andoni and Peilin Zhong.\n\nRescheduled to 06/1
8/2020 (originally scheduled for the 06/10/2020).\n
END:VEVENT
BEGIN:VEVENT
SUMMARY:Richard Peng (Georgia Tech)
DTSTART;VALUE=DATE-TIME:20200917T170000Z
DTEND;VALUE=DATE-TIME:20200917T180000Z
DTSTAMP;VALUE=DATE-TIME:20201031T035238Z
UID:TCSPlus/9
DESCRIPTION:Title: Solving Sparse Linear Systems Faster than Matrix Multip
lication\nby Richard Peng (Georgia Tech) as part of TCS+\n\nAbstract: TBA\
n
END:VEVENT
BEGIN:VEVENT
SUMMARY:Fotis Iliopoulos (IAS)
DTSTART;VALUE=DATE-TIME:20200923T170000Z
DTEND;VALUE=DATE-TIME:20200923T180000Z
DTSTAMP;VALUE=DATE-TIME:20201031T035238Z
UID:TCSPlus/10
DESCRIPTION:Title: Stochastic Local Search and the Lovasz Local Lemma\nby
Fotis Iliopoulos (IAS) as part of TCS+\n\nAbstract: TBA\n
END:VEVENT
BEGIN:VEVENT
SUMMARY:Alex Wein (NYU)
DTSTART;VALUE=DATE-TIME:20200930T170000Z
DTEND;VALUE=DATE-TIME:20200930T180000Z
DTSTAMP;VALUE=DATE-TIME:20201031T035238Z
UID:TCSPlus/11
DESCRIPTION:Title: Low-Degree Hardness of Random Optimization Problems\nby
Alex Wein (NYU) as part of TCS+\n\n\nAbstract\nIn high-dimensional statis
tical problems (including planted clique\, sparse PCA\, community detectio
n\, etc.)\, the class of "low-degree polynomial algorithms" captures many
leading algorithmic paradigms such as spectral methods\, approximate messa
ge passing\, and local algorithms on sparse graphs. As such\, lower bounds
against low-degree algorithms constitute concrete evidence for average-ca
se hardness of statistical problems. This method has been widely successfu
l at explaining and predicting statistical-to-computational gaps in these
settings.\n\nWhile prior work has understood the power of low-degree algor
ithms for problems with a "planted" signal\, we consider here the setting
of "random optimization problems" (with no planted signal)\, including the
problem of finding a large independent set in a random graph\, as well as
the problem of optimizing the Hamiltonian of mean-field spin glass models
. I will define low-degree algorithms in this setting\, argue that they ca
pture the best known algorithms\, and explain new proof techniques for giv
ing lower bounds against low-degree algorithms in this setting. The proof
involves a variant of the so-called "overlap gap property"\, which is a st
ructural property of the solution space.\n\nBased on joint work with David
Gamarnik and Aukosh Jagannath\, available at: https://arxiv.org/abs/2004.
12063\n
END:VEVENT
BEGIN:VEVENT
SUMMARY:Susanna F. de Rezende (Mathematical Institute of the Czech Academy
of Sciences)
DTSTART;VALUE=DATE-TIME:20201007T170000Z
DTEND;VALUE=DATE-TIME:20201007T180000Z
DTSTAMP;VALUE=DATE-TIME:20201031T035238Z
UID:TCSPlus/12
DESCRIPTION:Title: Lifting with Simple Gadgets and Applications to Circuit
and Proof Complexity\nby Susanna F. de Rezende (Mathematical Institute of
the Czech Academy of Sciences) as part of TCS+\n\n\nAbstract\nLifting the
orems in complexity theory are a method of transferring lower bounds in a
weak computational model into lower bounds for a more powerful computation
al model\, via function composition. There has been an explosion of liftin
g theorems in the last ten years\, essentially reducing communication lowe
r bounds to query complexity lower bounds. These theorems only hold for co
mposition with very specific "gadgets" such as indexing and inner product.
\n \nIn this talk\, we will present a generalization of the theorem liftin
g Nullstellensatz degree to monotone span program size by Pitassi and Robe
re (2018) so that it works for any gadget with high enough rank\, in parti
cular\, for useful gadgets such as equality and greater-than. We will then
explain how to apply our generalized theorem to solve three open problems
:\n\n- We present the first result that demonstrates a separation in proof
power for cutting planes with unbounded versus polynomially bounded coeff
icients. Specifically\, we exhibit CNF formulas that can be refuted in qua
dratic length and constant line space in cutting planes with unbounded coe
fficients\, but for which there are no refutations in subexponential lengt
h and subpolynomial line space if coefficients are restricted to be of pol
ynomial magnitude.\n\n- We give the strongest separation to-date between m
onotone Boolean formulas and monotone Boolean circuits. Namely\, we show t
hat the classical GEN problem\, which has polynomial-size monotone Boolean
circuits\, requires monotone Boolean formulas of size $2^{\\Omega(n / \\t
ext{polylog}(n))}$.\n\n- We give the first explicit separation between mon
otone Boolean formulas and monotone real formulas. Namely\, we give an exp
licit family of functions that can be computed with monotone real formulas
of nearly linear size but require monotone Boolean formulas of exponentia
l size. Previously only a non-explicit separation was known.\n\nThis talk
is based on joint work with Or Meir\, Jakob Nordström\, Toniann Pitassi\,
Robert Robere\, and Marc Vinyals.\n
END:VEVENT
BEGIN:VEVENT
SUMMARY:Jayadev Acharya (Cornell)
DTSTART;VALUE=DATE-TIME:20201014T170000Z
DTEND;VALUE=DATE-TIME:20201014T180000Z
DTSTAMP;VALUE=DATE-TIME:20201031T035238Z
UID:TCSPlus/13
DESCRIPTION:Title: Distributed Statistical Inference under Local Informati
on Constraints\nby Jayadev Acharya (Cornell) as part of TCS+\n\n\nAbstract
\nWe consider statistical inference tasks in a distributed setting where a
ccess to data samples is subjected to strict "local constraints\," through
a unified framework that captures communication limitations and (local) p
rivacy constraints as special cases. We study estimation (learning) and go
odness-of-fit (testing) for both discrete and high-dimensional distributio
ns. Our goal is to understand how the sample complexity increases under th
e information constraints.\n\nIn this talk we will provide an overview of
this field and a sample of some of our results. We will discuss the role o
f (public) randomness and interactivity in information-constrained infere
nce\, and make a case for thinking about randomness and interactivity as r
esources.\n\nThe work is part of a long-term ongoing collaboration with Cl
ément Canonne (IBM Research) and Himanshu Tyagi (IISc)\, and includes wor
ks done with Cody Freitag (Cornell)\, Yanjun Han (Stanford)\, Yuhan Liu (C
ornell)\, and Ziteng Sun (Cornell).\n
END:VEVENT
BEGIN:VEVENT
SUMMARY:Aayush Jain (UCLA)
DTSTART;VALUE=DATE-TIME:20201021T170000Z
DTEND;VALUE=DATE-TIME:20201021T180000Z
DTSTAMP;VALUE=DATE-TIME:20201031T035238Z
UID:TCSPlus/14
DESCRIPTION:Title: Indistinguishability Obfuscation from Well-Founded Assu
mptions\nby Aayush Jain (UCLA) as part of TCS+\n\nAbstract: TBA\n
END:VEVENT
BEGIN:VEVENT
SUMMARY:Omar Montasser (TTIC)
DTSTART;VALUE=DATE-TIME:20201028T170000Z
DTEND;VALUE=DATE-TIME:20201028T180000Z
DTSTAMP;VALUE=DATE-TIME:20201031T035238Z
UID:TCSPlus/15
DESCRIPTION:Title: Adversarially Robust Learnability: Characterization and
Reductions\nby Omar Montasser (TTIC) as part of TCS+\n\n\nAbstract\nWe st
udy the question of learning an adversarially robust predictor from uncorr
upted samples. We show that any VC class H is robustly PAC learnable\, but
we also show that such learning must sometimes be improper (i.e. use pred
ictors from outside the class)\, as some VC classes are not robustly prope
rly learnable. In particular\, the popular robust empirical risk minimiza
tion approach (also known as adversarial training)\, which is proper\, can
not robustly learn all VC classes. After establishing learnability\, we t
urn to ask whether having a tractable non-robust learning algorithm is suf
ficient for tractable robust learnability and give a reduction algorithm f
or robustly learning any hypothesis class H using a non-robust PAC learner
for H\, with nearly-optimal oracle complexity.\n\nThis is based on joint
work with Steve Hanneke and Nati Srebro\, available at https://arxiv.org/a
bs/1902.04217 and https://arxiv.org/abs/2010.12039..\n
END:VEVENT
BEGIN:VEVENT
SUMMARY:Shalev Ben-David (U Waterloo)
DTSTART;VALUE=DATE-TIME:20201104T180000Z
DTEND;VALUE=DATE-TIME:20201104T190000Z
DTSTAMP;VALUE=DATE-TIME:20201031T035238Z
UID:TCSPlus/16
DESCRIPTION:Title: Forecasting Algorithms\, Minimax Theorems\, and Randomi
zed Lower Bounds\nby Shalev Ben-David (U Waterloo) as part of TCS+\n\n\nAb
stract\nI will present a new approach to randomized lower bounds\, particu
larly in the setting where we wish to give a fine-grained analysis of rand
omized algorithms that achieve small bias. The approach is as follows: ins
tead of considering ordinary randomized algorithms which give an output in
{0\,1} and may err\, we switch models to look at "forecasting" randomized
algorithms which output a confidence in [0\,1] for whether they think the
answer is 1. When scored by a proper scoring rule\, the performance of th
e best forecasting algorithm is closely related to the bias of the best (o
rdinary) randomized algorithm\, but is more amenable to analysis.\n\nAs an
application\, I'll present a new minimax theorem for randomized algorithm
s\, which can be viewed as a strengthening of Yao's minimax theorem. Yao's
minimax theorem guarantees the existence of a hard distribution for a fun
ction f such that solving f against this distribution (to a desired error
level) is as hard as solving f in the worst case (to that same error level
). However\, the hard distribution provided by Yao's theorem depends on th
e chosen error level. Our minimax theorem removes this dependence\, giving
a distribution which certifies the hardness of f against all bias levels
at once. In recent work\, we used this minimax theorem to give a tight com
position theorem for randomized query complexity.\n\nBased on joint work w
ith Eric Blais.\n
END:VEVENT
BEGIN:VEVENT
SUMMARY:Shuai Shao (University of Wisconsin-Madison)
DTSTART;VALUE=DATE-TIME:20201111T180000Z
DTEND;VALUE=DATE-TIME:20201111T190000Z
DTSTAMP;VALUE=DATE-TIME:20201031T035238Z
UID:TCSPlus/17
DESCRIPTION:by Shuai Shao (University of Wisconsin-Madison) as part of TCS
+\n\nAbstract: TBA\n
END:VEVENT
BEGIN:VEVENT
SUMMARY:Sumegha Garg (Harvard)
DTSTART;VALUE=DATE-TIME:20201125T180000Z
DTEND;VALUE=DATE-TIME:20201125T190000Z
DTSTAMP;VALUE=DATE-TIME:20201031T035238Z
UID:TCSPlus/18
DESCRIPTION:Title: The Coin Problem with Applications to Data Streams\nby
Sumegha Garg (Harvard) as part of TCS+\n\nAbstract: TBA\n
END:VEVENT
BEGIN:VEVENT
SUMMARY:Yang Liu (Stanford University)
DTSTART;VALUE=DATE-TIME:20201202T180000Z
DTEND;VALUE=DATE-TIME:20201202T190000Z
DTSTAMP;VALUE=DATE-TIME:20201031T035238Z
UID:TCSPlus/19
DESCRIPTION:Title: Faster Divergence Maximization for Faster Maximum Flow\
nby Yang Liu (Stanford University) as part of TCS+\n\nAbstract: TBA\n
END:VEVENT
END:VCALENDAR