Speaker: Hung Le

\nAffiliation: University of Massachus
etts\, Amherst

Title: Reliable Spanners: Locality-Sensitive Orderi ngs Strike Back

\nAbstract:

\nA highly desirable property of n
etworks is robustness to failures.

\nConsider a metric space $(X\,d_X
)$\, a graph $H$ over $X$ is a $\\vartheta$-reliable $t$-spanner if\, for
every set of failed vertices $B\\subset X$\, there is a superset $B^+\\sup
seteq B$ such that the induced subgraph $H[X\\setminus B]$ preserves all t
he distances between points in $X\\setminus B^+$ up to a stretch factor $t
$\, while the expected size of $B^+$ is as most $(1+\\vartheta)|B|$. Such
a spanner could withstand a catastrophe: failure of even $90\\%$ of the ne
twork.

Buchin\, Har-Peled\, and Olah showed how to construct a spa rse reliable spanner for Euclidean space from Euclidean locality-sensitive orderings\, an object introduced by Chan\, Har-Peled\, and Jones. In this talk\, we extend their approach to non-Euclidean metric spaces by general izing the ordering of Chan\, Har-Peled\, and Jones to doubling metrics and introducing new types of locality-sensitive orderings for other metric sp aces. We also show how to construct reliable spanners from the newly intro duced locality-sensitive orderings via reliable 2-hop spanners for paths. The highlight of our results is that the number of edges in our spanner ha s no dependency on the spread.

DTSTART;TZID=America/New_York:20210303T120000 DTEND;TZID=America/New_York:20210303T130000 LOCATION:https://wse.zoom.us/j/91450299380 SEQUENCE:0 SUMMARY:[Theory Seminar] Hung Le URL:https://www.cs.jhu.edu/~mdinitz/theory/event/theory-seminar-hung-le/ X-COST-TYPE:free END:VEVENT BEGIN:VEVENT UID:ai1ec-356@www.cs.jhu.edu/~mdinitz/theory DTSTAMP:20240229T222828Z CATEGORIES: CONTACT: DESCRIPTION:Speaker: Teodor Marinov

\nAffiliation: Johns Hopkins Un
iversity

Title: Beyond Value-Function Gaps: Improved Instance-Depe ndent Regret Bounds for Episodic Reinforcement Learning

\nAbstract:< br />\nReinforcement Learning (RL) is a general scenario where agents inte ract with the environment to achieve some goal. The environment and an age nt’s interactions are typically modeled as a Markov decision process (MDP) \, which can represent a rich variety of tasks. But\, for which MDPs can a n agent or an RL algorithm succeed? This requires a theoretical analysis o f the complexity of an MDP. In this talk I will present information-theore tic lower bounds for a large class of MDPs. The lower bounds are based on studying a certain semi-infinite LP. Further\, I will show that existing a lgorithms enjoy tighter gap-dependent regret bounds (similar to the stocha stic multi-armed bandit problem)\, however\, they are unable to achieve th e information-theoretic lower bounds even in deterministic transition MDPs \, unless there is a unique optimal policy.

DTSTART;TZID=America/New_York:20210310T120000 DTEND;TZID=America/New_York:20210310T130000 LOCATION:https://wse.zoom.us/j/91450299380 SEQUENCE:0 SUMMARY:[Theory Seminar] Teodor Marinov URL:https://www.cs.jhu.edu/~mdinitz/theory/event/theory-seminar-teodor-mari nov/ X-COST-TYPE:free END:VEVENT BEGIN:VEVENT UID:ai1ec-355@www.cs.jhu.edu/~mdinitz/theory DTSTAMP:20240229T222828Z CATEGORIES: CONTACT: DESCRIPTION:Speaker: Dominik Kempa

\nAffiliation: Johns Hopkins Uni
versity

Title: How to store massive sequence collections in a sear chable form

\nAbstract:

\nCompressed indexing is concerned with
the design and construction of data structures to store massive sequences
in space close to the size of compressed data\, while simultaneously prov
iding searching functionality (such as pattern matching) on the original u
ncompressed data. These indexes have a huge impact on the analysis of larg
e-scale DNA databases (containing hundreds of thousands of genomes) but un
til recently the size of many indexes lacked theoretical guarantees and th
eir construction remains a computational bottleneck.

In this talk I will describe my work proving theoretical guarantees on index size as a function of compressed data size\, resolving a key open question in this f ield. Related to that\, I will also describe new algorithms for converting between two conceptually distinct compressed representations\, Lempel-Ziv and the Burrows-Wheeler Transform. I will show how these new findings ena ble advanced computation directly on compressed data. I will conclude by d escribing avenues for future work\, including the new algorithms for the c onstruction of compressed indexes that have the potential to cut indexing time by further orders of magnitude\, unlocking the ability to search trul y enormous text or DNA datasets.

DTSTART;TZID=America/New_York:20210317T120000 DTEND;TZID=America/New_York:20210317T130000 LOCATION:https://wse.zoom.us/j/91450299380 SEQUENCE:0 SUMMARY:[Theory Seminar] Dominik Kempa URL:https://www.cs.jhu.edu/~mdinitz/theory/event/theory-seminar-dominik-kem pa/ X-COST-TYPE:free END:VEVENT BEGIN:VEVENT UID:ai1ec-353@www.cs.jhu.edu/~mdinitz/theory DTSTAMP:20240229T222828Z CATEGORIES: CONTACT: DESCRIPTION:Speaker: Audra McMillan

\nAffiliation: Apple

Ti tle: Hiding among the clones: a simple and nearly optimal analysis of priv acy amplification by shuffling

\nAbstract:

\nDifferential priva
cy (DP) is a model of privacy-preserving machine learning that has garnere
d significant interest in recent years due to its rigorous privacy guarant
ees. An algorithm differentially private if the output is stable under sma
ll changes in the input database. While DP has been adopted in a variety o
f applications\, most applications of DP in industry actually satisfy a st
ronger notion called local differential privacy. In local differential pri
vacy data subjects perturb their data before it reaches the data analyst.
While this requires less trust\, it comes a substantial cost to accuracy.
Recent work of Erlingsson\, Feldman\, Mironov\, Raghunathan\, Talwar\, and
Thakurta [EFMRTT19] demonstrated that random shuffling amplifies differen
tial privacy guarantees of locally randomized data. Such amplification imp
lies substantially stronger privacy guarantees for systems in which data i
s contributed anonymously [BEMMRLRKTS17] and has led to significant intere
st in the shuffle model of privacy [CSUZZ19\, EFMRTT19]. In this talk\, we
will discuss a new result on privacy amplification by shuffling\, which a
chieves the asymptotically optimal dependence in the local privacy paramet
er. Our result is based on a new proof strategy which is simpler than prev
ious approaches\, and extends to a lightly weaker notion known as approxim
ate differential privacy with nearly the same guarantees. Based on joint w
ork with Vitaly Feldman and Kunal Talwar (https://arxiv.org/abs/2012.12803
)

Speaker: Maryam Negahbani

\nAffiliation: Dartmouth Univ
ersity

Title: “Revisiting Priority k-Center: Fairness and Outliers

\nAbstract:

\nClustering is a fundamental unsupervised learnin
g and facility location problem extensively studied in the literature. I w
ill talk about a clustering problem called “priority k-center” introduced
by Plesnik (in Disc. Appl. Math. 1987). Given a metric space on n points
X\, with distance function d\, an integer k\, and radius r_v for each poin
t v in X\, the goal is to choose k points S as “centers” to minimize the m
aximum distance of a point v to S divided by r_v. For uniform r_v’s this i
s precisely the “k-center” problem where the objective is to minimize the
maximum distance of any point to S. In the priority version\, points with
smaller r_v are prioritized to be closer to S. Recently\, a special case o
f this problem was studied in the context of “individually fair clustering
” by Jung et al.\, FORC 2020. This notion of fairness forces S to open a
center in every “densely populated area” by setting r_v to be v’s distance
to its closest (n/k)-th neighbor.

In this talk\, I show how to ap proximate priority k-center with outliers: When for a given integer z\, yo u are allowed to throw away z points as outliers and minimize the objectiv e over the rest of the points. We show there is 9-approximation\, which is morally a 5\, if you have constant many types of radii or if your radii a re powers of 2. This is via an LP-aware reduction to min-cost max-flow and is general enough that could handle Matroid constraints on facilities (wh ere instead of asking to pick at most k facilities\, you are asked to pick facilities that are independent in a given matroid). Things become quite interesting for priority knapsack-center with outliers: where opening each center costs something and you have a limited budget to spend on your sol ution S. In this case\, we do not know how to solve the corresponding flow problem\, so we alter our reduction to reduce to a simpler problem we do know how to solve taking a hit of +5 in the approximation ratio. There are still many open problems in this work\, in addition to solving the flow p roblem in the knapsack case\, the best LP integrality gap we know for prio rity k-center with outliers is 3.

DTSTART;TZID=America/New_York:20210331T120000 DTEND;TZID=America/New_York:20210331T130000 LOCATION:https://wse.zoom.us/j/91450299380 SEQUENCE:0 SUMMARY:[Theory Seminar] Maryam Negahbani URL:https://www.cs.jhu.edu/~mdinitz/theory/event/theory-seminar-maryam-nega hbani/ X-COST-TYPE:free END:VEVENT BEGIN:VEVENT UID:ai1ec-346@www.cs.jhu.edu/~mdinitz/theory DTSTAMP:20240229T222828Z CATEGORIES: CONTACT: DESCRIPTION:Speaker: Leonidas Tsepenekas

\nAffiliation: University
of Maryland

Title: Approximating Two-Stage Stochastic Supplier Pro blems

\nAbstract:

\nThe main focus of this talk will be radius-
based (supplier) clustering in the two-stage stochastic setting with recou
rse\, where the inherent stochasticity of the model comes in the form of a
budget constraint. Our eventual goal is to provide results in the most ge
neral distributional setting\, where there is only black-box access to the
underlying distribution. To that end\, we follow a two-step approach. Fir
st\, we develop algorithms for a restricted version of the problem\, in wh
ich all possible scenarios are explicitly provided\; second\, we employ a
novel scenario-discarding variant of the standard Sample Average Approxima
tion (SAA) method\, in which we also crucially exploit structural properti
es of the algorithms developed for the first step of the framework. In thi
s way\, we manage to generalize the results of the latter to the black-box
model. Finally\, we note that the scenario-discarding modification to the
SAA method is necessary in order to optimize over the radius.

Pap er: https://arxiv.org/abs/2008.03325

DTSTART;TZID=America/New_York:20210407T120000 DTEND;TZID=America/New_York:20210407T130000 LOCATION:https://wse.zoom.us/j/91450299380 SEQUENCE:0 SUMMARY:[Theory Seminar] Leonidas Tsepenekas URL:https://www.cs.jhu.edu/~mdinitz/theory/event/theory-seminar-leonidas-ts epenekas/ X-COST-TYPE:free END:VEVENT BEGIN:VEVENT UID:ai1ec-358@www.cs.jhu.edu/~mdinitz/theory DTSTAMP:20240229T222828Z CATEGORIES: CONTACT: DESCRIPTION:Speaker: Samson Zhou

\nAffiliation: Carnegie Mellon Uni
versity

Title: Tight Bounds for Adversarially Robust Streams and S liding Windows via Difference Estimators

\nAbstract:

\nWe intro
duce *difference estimators* for data stream computation\, which pr
ovide approximations to F(v)-F(u) for frequency vectors v\,u and a given f
unction F. We show how to use such estimators to carefully trade error for
memory in an iterative manner. The function F is generally non-linear\, a
nd we give the first difference estimators for the frequency moments F_p f
or p between 0 and 2\, as well as for integers p>2. Using these\, we resol
ve a number of central open questions in adversarial robust streaming and
sliding window models.

For both models\, we obtain algorithms for norm estimation whose dependence on epsilon is 1/epsilon^2\, which shows\, up to logarithmic factors\, that there is no overhead over the standard i nsertion-only data stream model for these problems.

DTSTART;TZID=America/New_York:20210414T120000 DTEND;TZID=America/New_York:20210414T130000 SEQUENCE:0 SUMMARY:[Theory Seminar] Samson Zhou URL:https://www.cs.jhu.edu/~mdinitz/theory/event/theory-seminar-samson-zhou -3/ X-COST-TYPE:free END:VEVENT BEGIN:VEVENT UID:ai1ec-376@www.cs.jhu.edu/~mdinitz/theory DTSTAMP:20240229T222828Z CATEGORIES: CONTACT: DESCRIPTION: DTSTART;TZID=America/New_York:20230906T120000 DTEND;TZID=America/New_York:20230906T130000 SEQUENCE:0 SUMMARY:[Theory Seminar] Welcome Back / Introductions URL:https://www.cs.jhu.edu/~mdinitz/theory/event/theory-seminar-welcome-bac k-introductions/ X-COST-TYPE:free END:VEVENT BEGIN:VEVENT UID:ai1ec-372@www.cs.jhu.edu/~mdinitz/theory DTSTAMP:20240229T222828Z CATEGORIES: CONTACT: DESCRIPTION:Speaker: Zeyu Guo

\nAffiliation: Ohio State University<
/p>\n

Title: TBD

\nAbstract: TBD

DTSTART;TZID=America/New_York:20231025T120000 DTEND;TZID=America/New_York:20231025T130000 SEQUENCE:0 SUMMARY:[Theory Seminar] Zeyu Guo URL:https://www.cs.jhu.edu/~mdinitz/theory/event/theory-seminar-zeyu-guo/ X-COST-TYPE:free END:VEVENT END:VCALENDAR