EnCORE

The Institute for Emerging CORE Methods in Data Science

Applications are now open for EnCORE Visitors Program

NEWS

Raghu Meka's work featured in Quanta as Biggest Breakthroughs in Math

Raghu Meka's and Zander Kelley's work on three-term arithmetic was selected as one of three mathematical breakthroughs in 2023 by Quanta Magazine.
Learn More

Rising Stars in Data Science 2023

Rising Stars in Data Science was hosted November 13-14,2023 by the University of Chicago with the University of California, San Diego – EnCORE and HDSI.
Learn More

Empowering Young Minds: Robotic Arts and Craft Workshop for Elementary School Kids

Saura Naderi of HDSI Lab 3.0 and EnCORE, brought together a group of elementary school students for an immersive workshop in robotics and creativity on Saturday, December 2.
Learn More

EnCORE: Call for Extended Research Visits & Workshops

EnCORE welcomes proposals for extended research visits between 2024 - 2025! Submit your proposals today.
Learn More

TCS for All scholarships to attend FOCS and STOC are available for minority students

TCS Women Travel Scholarships are intended for researchers at the beginning of their career. This scholarship is being made available for women and minorities, this scholarship is open to both US and international students.
Learn More

Surprise Computer Science Proof Stuns Mathematicians

Zander Kelley and Raghu Meka make a mathematical breakthrough on one of the biggest unsolved problems in the field of additive combinatorics.
Learn More

Understanding Self Distillation in the Presence of Label Noise

This study explores the phenomenon of the "student" model outperforming the "teacher" model in self-distillation (SD) with the presence of noise, while formalizing the limitations of SD.
Learn More

U.S. census data vulnerable to attack without enhanced privacy measures

A new PNAS has revealed that the statistics published by the U.S. Census Bureau can be reverse-engineered, revealing private information about individual respondents.
Learn More

A Mathematical Breakthrough by the EnCORE Faculty Raghu Meka

Absolutely Sensational Morning News – Zander Kelley and Raghu Meka proved Behrend-type bounds for 3APs.
Learn More

Expand Foundations of Data Science

To learn more contact: barnas@ucsd.edu with the subject line Expand TRIPODS
Learn More
EnCORE is hiring for a Postdoctoral Position
Learn More

New $10M NSF-Funded Institute Will Get to the CORE of Data Science

EnCORE will join three other NSF-funded institutes in the country dedicated to the exploration of data science through the NSF’s Transdisciplinary Research in Principles of Data Science Phase II (TRIPODS) program.
Learn More

UCLA Part of New $10M NSF Data Science Research Center, EnCORE

UCLA will be part of a multi-institutional research center funded by the National Science Foundation (NSF).
Learn More

$10M NSF-Funded Institute Will Get to the CORE of Data Science

New $10M NSF-Funded Institute Will Get to the CORE of Data Science. EnCORE will tackle important problems in foundations of Data Science
Learn More

NSF Awards

New NSF awards will advance theoretical foundations of data science research through interdisciplinary collaborations
Learn More

Data Science Theory

Join our Youtube Channel!

Data Science Theory

Join our Youtube Channel to learn more on Foundation of Data Science Series!
Learn More

Computation+Compression

workshop received an overwhelming response. Registration had to be closed at 500 registered participants.

Computation+Compression

Recording of all talks on Computation+Compression workshop are now available.
Visit Website

Masters of Data Science Online

Applications now open!

Masters of Data Science Online

Applications for Masters of Data Science Online is now open for Fall 2022 at HDSI.
Learn More

New Book Announcement:

Computational Topology for Data Analysis. T.K. Dey, and Y. Wang. Forthcoming book, Cambridge University Press, 2021
Computational Topology for Data Analysis. T.K. Dey, and Y. Wang. Forthcoming book, Cambridge University Press, 2021 [PDF version avaliable]
Learn More

General Chair of ICML

Chaudhuri will be the General Chair of ICML 2022.

Chaudhuri will be the General Chair of ICML 2022.

First cohort of Ph.D. students in Data Science

HDSI will be welcoming the first cohort of Ph.D. students in Data Science in Fall 2022.

HDSI

HDSI will be welcoming the first cohort of Ph.D. students in Data Science in Fall 2022. Apply now!
Learn More

Congratulations to Professor Yusu Wang

as ACM Distinguished Memeber.
Congratulations to Professor Yusu Wang on her recognition as ACM Distinguished Member for outstanding scientific contributions to computing!
Learn More

General Chair of STOC 2023

Saha will be the General Chair of STOC 2023.

Saha will be the General Chair of STOC 2023.

I am Data Science

Mazumdar featured in I am Data Science series.

Mazumdar featured in I am Data Science series.

Learn More

EnCORE: Call for Extended Research Visits & Workshops

EnCORE welcomes proposals for extended research visits between 2024 - 2025! Submit your proposals today.
Learn More

Old Questions and New Directions in Clustering

EnCORE is hosting a 3-day workshop to reinvigorate collaboration between the approximation and computational geometry communities.
Learn More

Follow us on Twitter

Subscribe to our YouTube Channel

EnCORE: The institute for Emerging CORE Methods in Data Science

The Institute for Emerging CORE Methods in Data Science, or EnCORE, is led by the
University of California San Diego in collaboration with the University of California, Los
Angeles; University of Pennsylvania; and The University of Texas at Austin. EnCORE brings
together scientists from multiple disciplines such as statistics, mathematics, electrical
engineering, theoretical computer science, machine learning and health science, among
others.
EnCORE’s team will focus on the four CORE pillars of data science: C for complexities of
data, O for optimization, R for responsible learning, and E for education and engagement.
The institute is fostering a plan for outreach and broadening participation by engaging
students of diverse backgrounds at all levels, from K-12 to postdocs and junior faculty. The
project aims to reach a wide demography of students by offering collaborative courses across
its partner universities and a flexible co-mentorship plan for multidisciplinary research.
To bring theoretical development into practice, EnCORE will work with industry partners
and domain scientists and will forge strong connections with other NSF Harnessing the Data
Revolution Institutes across the nation.

NSF’s Harnessing the Data Revolution (HDR) Big Idea is a national scale activity to enable new modes of data-driven discovery that will allow fundamental questions to be asked and answered at the frontiers of science and  engineering. HDR TRIPODS aims to bring together the electrical engineering, mathematics, statistics, and theoretical computer science communities together through integrated research and training activities. 

Pareto-Optimal Algorithms for Learning in Games

Natalie Collina and Eshwar Ram Arunachaleswaran

Abstract: We study the problem of characterizing optimal learning algorithms for playing repeated games against an adversary with unknown payoffs. In this problem, the first player (called the learner) commits to a learning algorithm against a second player (called the optimizer), and the optimizer best-responds by choosing the optimal dynamic strategy for their (unknown but well-defined) payoff. Classic learning algorithms (such as no-regret algorithms) provide some counterfactual guarantees for the learner, but might perform much more poorly than other learning algorithms against particular optimizer payoffs.

In this paper, we introduce the notion of asymptotically Pareto-optimal learning algorithms. Intuitively, if a learning algorithm is Pareto-optimal, then there is no other algorithm which performs asymptotically at least as well against all optimizers and performs strictly better (by at least $\Omega(T)$) against some optimizer. We show that well-known no-regret algorithms such as Multiplicative Weights and Follow The Regularized Leader are Pareto-dominated. However, while no-regret is not enough to ensure Pareto-optimality, we show that a strictly stronger property, no-swap-regret, is a sufficient condition for Pareto-optimality.

Proving these results requires us to address various technical challenges specific to repeated play, including the fact that there is no simple characterization of how optimizers who are rational in the long-term best-respond against a learning algorithm over multiple rounds of play. To address this, we introduce the idea of the asymptotic menu of a learning algorithm: the convex closure of all correlated distributions over strategy profiles that are asymptotically implementable by an adversary. Interestingly, we show that all no-swap-regret algorithms share the same asymptotic menu, implying that all no-swap-regret algorithms are “strategically equivalent”.

This talk is based on work with Jon Schneider.

Metric Learning from Lazy Crowds

Geelon So

Abstract: We consider crowd-based metric learning from preference comparisons, where given two items, a user prefers the item that is closer to their latent ideal item. Here, “closeness” is measured with respect to a shared but unknown Mahalanobis distance. Can we recover this distance when we can only obtain very few responses per user?

In this very low-budget regime, we show that generally, nothing at all about the metric is revealed, even with infinitely many users. But when the items have subspace cluster structure, we present a divide-and-conquer approach for metric recovery, and provide theoretical recovery guarantees and empirical validation.

This is joint work with Zhi Wang (UCSD) and Ramya Korlakai Vinayak (UW–Madison).

Random Walks, Conductance, and Resistance for the Connection Graph Laplacian

Zhengchao Wan

Abstract: We investigate the concept of effective resistance in connection graphs, expanding its traditional application from undirected graphs. We propose a robust definition of effective resistance in connection graphs by focusing on the duality of Dirichlet-type and Poisson-type problems on connection graphs. Additionally, we delve into random walks, taking into account both node transitions and vector rotations. This approach introduces novel concepts of effective conductance and resistance matrices for connection graphs, capturing mean rotation matrices corresponding to random walk transitions. Thereby, it provides new theoretical insights for network analysis and optimization.

This is based on a joint work with Alexander Cloninger, Gal Mishne, Andreas Oslandsbotn, Sawyer Jack Robertson and Yusu Wang.

Approximability and Inapproximability of Strict-CSPs

Akbar Rafiey

Abstract: We study the approximability and inapproximability of Strict-CSPs. An instance of the Strict-CSPs consists of a set of constraints over a set of variables and a cost function over the assignments. The goal is to find an assignment to the variables of minimum cost which satisfies all the constraints. Some prominent problems that this framework captures are (Hypergraph) Vertex Cover, Min Sum k-Coloring, Multiway Cut, Min Ones, and others.

We focus on a systematic study of Strict-CSPs of the form Strict-CSPs(H), that is, Strict-CSPs where the type of constraints is limited to predicates from a set H. Our first result is a dichotomy for approximation of Strict-CSPs(H), where H is a binary predicate, i.e., a digraph. We prove that if digraph H has bounded width, then Strict-CSPs(H) is approximable within a constant factor (depending on H); otherwise, there is no approximation for Strict-CSPs(H) unless P=NP.

Second, we study the inapproximability of Strict-CSP and present the first general hardness of approximation for Strict-CSP. More precisely, we prove a dichotomy theorem that states every instance of Strict-CSP(H) (H being a digraph) is either polynomial-time solvable or APX-complete. Moreover, we show the existence of a universal constant 0<\delta<1 such that it is NP-hard to approximate Strict-CSP(H) within a factor of (2-\delta) for all digraphs H where Strict-CSP(H) is NP-complete.

Buy-many Mechanisms for Many Unit-demand Buyers

Rojin Rezvan

Abstract: A recent line of research has established a novel desideratum for designing approximatelyrevenue-optimal multi-item mechanisms, namely the buy-many constraint. Under this constraint, prices for different allocations made by the mechanism must be subadditive implying that the price of a bundle cannot exceed the sum of prices of individual items it contains. This natural constraint has enabled several positive results in multi-item mechanism design bypassing well-established impossibility results. Our work addresses a main open question from this literature involving the design of buymany mechanisms for multiple buyers. Our main result is that a simple sequential item pricing mechanism with buyer-specific prices can achieve an O(log m) approximation to the revenue of any buy-many mechanism when all buyers have unit-demand preferences over m items. This is the best possible as it directly matches the previous results for the single-buyer setting where no simple mechanism can obtain a better approximation. Our result applies in full generality: even though there are many alternative ways buy-many mechanisms can be defined for multibuyer settings, our result captures all of them at the same time. We achieve this by directly competing with a more permissive upper-bound on the buy-many revenue, obtained via an ex-ante relaxation.

Streaming PCA for Markovian Data

Syamantak Kumar

Abstract: Since its inception in 1982, Oja’s algorithm has become an established method for streaming principle component analysis (PCA). We study the problem of streaming PCA, where the data-points are sampled from an irreducible, aperiodic, and reversible Markov chain. Our goal is to estimate the top eigenvector of the unknown covariance matrix of the stationary distribution. This setting has implications in scenarios where data can solely be sampled from a Markov Chain Monte Carlo (MCMC) type algorithm, and the objective is to perform inference on parameters of the stationary distribution. Most convergence guarantees for Oja’s algorithm in the literature assume that the data-points are sampled IID. For data streams with Markovian dependence, one typically downsamples the data to get a “nearly” independent data stream. In this paper, we obtain the first sharp rate for Oja’s algorithm on the entire data, where we remove the logarithmic dependence on the sample size, resulting from throwing data away in downsampling strategies.

A d^{1/2 + o(1)} Monotonicity Tester for Boolean Functions on d-Dimensional Hypergrids

Hadley Black

Abstract: Monotonicity testing of Boolean functions over the n-width, d-dimensional hypergrid is a classic problem in property testing, where the goal is to design a randomized algorithm which can distinguish monotone functions from those which are far from any monotone function while making as few queries as possible. The special case of n = 2 corresponds to the hypercube domain. Here a long line of works exploiting a very interesting connection with isoperimetric inequalities for Boolean functions culminated in a non-adaptive tester making ~O(d^{1/2}) queries in a celebrated paper by Khot, Minzer, and Safra (SICOMP 2018). This is known to be optimal for non-adaptive testers. However, the general case of hypergrids for n > 2 remained open. Very recently, two papers (Black-Chakrabarty-Seshadhri STOC 2023 and Braverman-Khot-Kindler-Minzer ITCS 2023) independently obtained ~O(poly(n) d^{1/2}) query testers for hypergrids. These results are essentially optimal for n < polylog(d), but are far from optimal for n >> polylog(d).

This talk covers our most recent result (appearing at FOCS 2023) which obtains a non-adaptive d^{1/2+o(1)} query tester for all n, resolving the non-adaptive monotonicity testing problem for hypergrids, up to a factor of d^{o(1)}. Our proof relies on many new techniques as well as two key theorems which we proved in earlier works from SODA 2020 and STOC 2023.

SmoothLLMs: Defending LLMs against Adversarial Attacks

Alex Robey

Abstract: Despite efforts to align large language models (LLMs) with human values, widely-used LLMs such as GPT, Llama, Claude, and PaLM are susceptible to jailbreaking attacks, wherein an adversary fools a targeted LLM into generating objectionable content.  To address this vulnerability, we propose SmoothLLM, the first algorithm designed to mitigate jailbreaking attacks on LLMs.  Based on our finding that adversarially-generated prompts are brittle to character-level changes, our defense first randomly perturbs multiple copies of a given input prompt, and then aggregates the corresponding predictions to detect adversarial inputs.  SmoothLLM reduces the attack success rate on numerous popular LLMs to below one percentage point, avoids unnecessary conservatism, and admits provable guarantees on attack mitigation.  Moreover, our defense uses exponentially fewer queries than existing attacks and is compatible with any LLM.

Composition of Nested Embeddings with an Application to Outlier Removal

Kristin Sheridan

Abstract: We study the design of embeddings into Euclidean space with outliers. Given a metric space $(X,d)$ and an integer $k$, the goal is to embed all but $k$ points in $X$ (called the “”outliers””) into $\ell_2$ with the smallest possible distortion $c$. Finding the optimal distortion $c$ for a given outlier set size $k$, or alternately the smallest $k$ for a given target distortion $c$ are both NP-hard problems. In fact, it is UGC-hard to approximate $k$ to within a factor smaller than $2$ even when the metric sans outliers is isometrically embeddable into $\ell_2$. We consider bi-criteria approximations. Our main result is a polynomial time algorithm that approximates the outlier set size to within an $O(\log^2 k)$ factor and the distortion to within a constant factor.

The main technical component in our result is an approach for constructing a composition of two given embeddings from subsets of $X$ into $\ell_2$ which inherits the distortions of each to within small multiplicative factors. Specifically, given a low $c_S$ distortion embedding from $S\subset X$ into $\ell_2$ and a high(er) $c_X$ distortion embedding from the entire set $X$ into $\ell_2$, we construct a single embedding that achieves the same  distortion $c_S$ over pairs of points in $S$ and an expansion of at most $O(\log k)\cdot c_X$ over the remaining pairs of points, where $k=|X\setminus S|$. Our composition theorem extends to embeddings into arbitrary $\ell_p$ metrics for $p\ge 1$, and may be of independent interest. While unions of embeddings over disjoint sets have been studied previously, to our knowledge, this is the first work to consider compositions of {\em nested} embeddings.

Graph Sparsification by Approximate Matrix Multiplication

Neo Charalambides

Abstract:  Graphs arising in statistical problems, signal processing, large networks, combinatorial optimization, and data analysis are often dense, which causes both computational and storage bottlenecks. One way of sparsifying a weighted graph, while sharing the same vertices as the original graph but reducing the number of edges, is through spectral sparsification. We study this problem through the perspective of RandNLA. Specifically, we utilize randomized matrix multiplication to give a clean and simple analysis of how sampling according to edge weights gives a spectral approximation to graph Laplacians, without requiring spectral information. Through the CR−MM algorithm, we attain a simple and computationally efficient sparsifier whose resulting Laplacian estimate is unbiased and of minimum variance. Furthermore, we define a new notion of additive spectral sparsifiers, which has not been considered in the literature.

Talk Title

Student Name

Abstract