8th TOCA-SV

Program

Morning Talks

10:30am-10:45am Jelani Nelson (UC Berkeley)

10:50am-11:05am Tselil Schramm (Stanford)

11:10am-11:25am Jacob Steinhardt (UC Berkeley)

11:30am-11:45am Nika Haghtalab (UC Berkeley)

Lunch Break

11:50am-1:00pm (lunch is provided)

Afternoon Talks

1:00pm-1:10pm David Wajc (Stanford)

1:10pm-1:20pm Erik Waingarten (Stanford)

1:20pm-1:30pm Thomas Steinke (Google)

1:30pm-1:40pm Katerina Soteraki (UC Berkeley)

1:40pm-1:50pm Inbal Livni Navon (Stanford)

—

2:05pm-2:15pm Jason Li (UC Berkeley)

2:15pm-2:25pm Frederic Koehler (Stanford)

2:25pm-2:35pm Michael Kim (UC Berkeley)

2:35pm-2:45pm Fotis Iliopoulos (Google)

—

3:00pm-3:10pm William Hoza (UC Berkeley)

3:10pm-3:20pm Guru Guruganesh (Google)

3:20pm-3:30pm Mahsa Derakhshan (UC Berkeley)

3:30pm-3:40pm Soheil Behnezhad (Stanford)

Poster Sessions

4:00pm-4:45pm (A)

4:45pm-5:30pm (B)

Talks

Speaker: Jelani Nelson

Title: Private Frequency Estimation via Projective Geometry

Abstract:
We propose a new algorithm ProjectiveGeometryResponse (PGR) for locally differentially private (LDP) frequency estimation. For a universe size of k and with n users, our ε-LDP algorithm has communication cost ⌈log2k⌉ bits in the private coin setting and εlog2e+O(1) in the public coin setting, and has computation cost O(n+kexp(ε)logk) for the server to approximately reconstruct the frequency histogram, while achieving optimal privacy/utility tradeoff, including optimality of the leading constant factor. Our empirical evaluation shows a speedup of over 50x over PI-RAPPOR (Feldman and Talwar; 2021), while using approximately 75x less memory for practically relevant parameter settings. In addition, the running time of our algorithm is within an order of magnitude of HadamardResponse (Acharya, Sun, and Zhang; 2019) and RecursiveHadamardResponse (Chen, Kairouz, and Ozgur; 2020) which have significantly worse reconstruction error. Our new algorithm is based on using Projective Planes over a finite field to define a small collection of sets that are close to being pairwise independent and a dynamic programming algorithm for approximate histogram reconstruction on the server side. We also give an extension of PGR, which we call HybridProjectiveGeometryResponse, that allows trading off computation time with utility smoothly.

Joint work with Vitaly Feldman (Apple), Huy Le Nguyen (Northeastern), and Kunal Talwar (Apple).

—

Speaker: Tselil Schramm

Title: Testing thresholds for high-dimensional random geometric graphs

Abstract:
We study random geometric graphs on the unit sphere in the high-dimensional setting, where the dimension grows to infinity with the number of vertices. Our central question is: given such a graph, when is it possible to identify the underlying geometry? As the dimension grows relative to the number of vertices, the edges in the graph become increasingly independent, and the underlying geometry becomes less apparent. In this talk I will present recent progress on this question: we show that in sparse geometric random graphs, if the dimension is at least polylogarithmic in the number of vertices, then the graphs are statistically indistinguishable from Erdos-Renyi graphs, and the underlying geometry disappears.

Based on joint work with Siqi Liu, Sidhanth Mohanty, and Elizabeth Yang.

—

Speaker: Jacob Steinhardt

Title: Supply-Side Equilibria in Recommender Systems

Abstract:
Digital recommender systems such as Spotify and Netflix affect not only consumer behavior but also producer incentives: producers seek to supply content that will be recommended by the system. But what content will be produced? To understand this, we model users and content as D-dimensional vectors, and assume the system recommends the content that has the highest dot product with each user. In contrast to traditional economic models, here the producer decision space is high-dimensional and the user base is heterogeneous. This gives rise to new qualitative phenomena at equilibrium: the formation of genres,and the possibility of positive profit at equilibrium. We characterize these phenomena in terms of the geometry of the users and the structure of producer costs. At a conceptual level, our work serves as a starting point to investigate how recommender systems shape supply-side competition between producers.

Joint work with Meena Jagadeesan and Nikhil Garg.

—

Speaker: Nika Haghtalab

Title/Abstract: TBA

—

Speaker: David Wajc

Title: Online edge coloring

Abstract:
Vizing's theorem asserts that the minimum number of colors needed to edge color a graph with maximum degree D is either D or D+1. How closely can we approximate this optimal coloring when the graph is revealed in an online fashion, either edge-by-edge or vertex-by-vertex? In this talk, I will outline a number of results for this problem by past and present members of the TCS community in the Bay Area.

—

Speaker: Erik Waingarten

Title: The Johnson-Lindenstrauss Lemma for Clustering and Subspace Approximation

Abstract:
The Johnson-Lindenstrauss lemma says that for any set of vectors in a high-dimensional space, there exists an embedding into a much lower dimensional space which approximately preserves all pairwise distances. Here, we explore dimensionality reduction for other geometric optimization problems: given a geometric optimization problem (for example, k-means clustering or principal components analysis) is there always an embedding to a lower dimensional space which approximately preserves the cost of the optimization? In this talk, I will overview a few results in this space, and present a new technique for using coreset constructions in order to get improved dimensionality reduction.

Joint with Moses Charikar.

—

Speaker: Thomas Steinke

Title: Hyperparameter Tuning with Renyi Differential Privacy

Abstract:
For many differentially private algorithms, such as the prominent noisy stochastic gradient descent (DP-SGD), the analysis needed to bound the privacy leakage of a single training run is well understood. However, few studies have reasoned about the privacy leakage resulting from the multiple training runs needed to fine tune the value of the training algorithm's hyperparameters. In this work, we first illustrate how simply setting hyperparameters based on non-private training runs can leak private information. Motivated by this observation, we then provide privacy guarantees for hyperparameter search procedures within the framework of Renyi Differential Privacy. Our results improve and extend the work of Liu and Talwar (STOC 2019). Our analysis supports our previous observation that tuning hyperparameters does indeed leak private information, but we prove that, under certain assumptions, this leakage is modest, as long as each candidate training run needed to select hyperparameters is itself differentially private.

Joint work with Nicolas Papernot. https://arxiv.org/abs/2110.03620

—

Speaker: Katerina Soteraki

Title: Sumcheck Arguments and their Applications

Abstract:
In this talk, I will present sumcheck arguments; a new class of interactive protocols which show that "split-and-fold protocols" (such as Bulletproofs and many more) are consequences of the Lund et al. sumcheck protocol from 1992. We show that many existing commitment schemes can be framed as "sumcheck-friendly commitments" over rings and modules, and we obtain succinct arguments for NP-complete statements over rings. This gives a lattice-based succinct argument from the SIS assumption, which was previously open.

—

Speaker: Inbal Livni Navon

Title: Hardness of Approximation of Parameterized Set Cover using Threshold Graphs from Error Correcting Codes

Abstract:
One of the methods to prove hardness of approximation results for parameterized problems is threshold graph composition, introduced by Lin [Lin18]. In this method, a no-gap instance of a parameterized problem is composed with a graph with special thresholding properties to create a gap instance of the problem.

In this talk I will show a construction of such threshold graphs from any error correcting code. The threshold graphs can then be used to prove hardness of approximation results for the parameterized set cover and label cover problems, under W[1] hardness or the exponential time hypothesis.

This is from a joint work with Karthik C.S.

—

Speaker: Jason Li

Title: Preconditioning and Locality in Algorithm Design

Abstract:
We highlight recent advances in graph algorithms for problems such as deterministic mincut, Steiner mincut, parallel shortest path, and more. The common theme behind these improvements are the concepts of preconditioning and locality, two simple ideas that have revolutionized the algorithmic field for the past two decades.

—

Speaker: Frederic Koehler

Title: Optimistic Rates in Gaussian Space

Abstract:
Optimistic rates are a type of generalization bound ("localized uniform convergence bound"), i.e. inequality relating test and training error of a predictor. The theory has been developed in several interesting works since its introduction by Vapnik and Chervonenkis in the 70s & 80s. Recently, we revisited these bounds in the context of Gaussian linear regression. In this context, optimistic rates theory can be made very tight and has interesting consequences.

Based on joint works with Lijia Zhou, Danica Sutherland, and Nathan Srebro.

—

Speaker: Michael Kim

Title: Planting Undetectable Backdoors in ML Models

Abstract:
Given the computational cost and technical expertise required to train machine learning models, users may delegate the task of learning to a service provider. We show how a malicious learner can plant an undetectable backdoor into a classifier. On the surface, such a backdoored classifier behaves normally, but in reality, the learner maintains a mechanism for changing the classification of any input, with only a slight perturbation. Importantly, without the appropriate "backdoor key", the mechanism is hidden and cannot be detected by any computationally-bounded observer. Our construction of undetectable backdoors also sheds light on the related issue of robustness to adversarial examples. By constructing undetectable backdoors for an “adversarially-robust” learning algorithm, we can produce a classifier that is indistinguishable from a robust classifier, but where every input has an adversarial example! In this way, the existence of undetectable backdoors represent a significant theoretical roadblock to certifying adversarial robustness.

Joint work with Shafi Goldwasser, Vinod Vaikuntanathan, Or Zamir.

—

Speaker: Fotis Iliopoulos

Title: Solving locally sparse constraint satisfaction problems up to the algorithmic barrier threshold.

Abstract:

Recent results imply that local sparsity is a sufficient property for coloring pseudo-random graphs up to the algorithmic barrier for random graphs.

In this talk I'll briefly review these results and discuss the question: "Is local sparsity a sufficient property for solving pseudo-random CSPs up to the corresponding algorithmic barrier for random instances?".

—

Speaker: William Hoza

Title: Depth-d Threshold Circuits vs. Depth-(d + 1) AND-OR Trees

Abstract:

For a positive integer n and d = o(log log n), we prove that there is a Boolean function F on n bits and a value γ = exp(-Θ(d)) such that F can be computed by a uniform depth-(d + 1) AC^0 circuit with O(n) wires, but F cannot be computed by any depth-d TC^0 circuit with n^{1 + γ} wires. This bound matches the current state-of-the-art lower bounds for computing explicit functions by threshold circuits of depth d > 2, which were previously known only for functions outside AC^0 such as the parity function. Furthermore, in our result, the AC^0 circuit computing F is a monotone read-once formula (i.e., an AND-OR tree), and the lower bound holds even in the average-case setting with respect to advantage n^{-γ}.

Our proof builds on the random projection procedure of Håstad, Rossman, Servedio, and Tan, which they used to prove the celebrated average-case depth hierarchy theorem for AC^0 (J. ACM, 2017). We show that under a modified version of their projection procedure, any depth-d threshold circuit with n^{1 + γ} wires simplifies to a near-trivial function, whereas an appropriately parameterized AND-OR tree of depth d + 1 maintains structure.

Joint work with Pooya Hatami, Avishay Tal, and Roei Tell.

—

Speaker: Guru Guruganesh

Title: Contextual Recommendations from Low Regret Cutting Planes

Abstract:
We consider the following variant of contextual linear bandits motivated by routing applications in navigational engines and recommendation systems. We wish to learn a hidden d-dimensional vector w. Every round, we are presented with a subset X_t ⊆ R^d of possible actions. If we choose (i.e. recommend to the user) action x_t, we obtain utility <w,x_t> but only learn the identity of the best action. We design algorithms for this problem which achieve regret O(d log T ) and exp(O(d log d)). To accomplish this, we use cutting-plane algorithms with low “regret” – the total distance between the true point w and the hyperplanes the separation oracle returns.

We also consider the variant where we are allowed to provide a list of several recommendations. In this variant, we give an algorithm with O(d^2 log d) regret and list size poly(d). Our results rely on new algorithmic techniques in convex geometry (including a variant of Steiner’s formula for the centroid of a convex set).

—

Speaker: Mahsa Derakhshan

Title: Max-Weight Online Stochastic Matching

Abstract:
Online algorithms are commonly compared against the best offline solution. That is, the benchmark, unlike the algorithm, is not bound to make its decisions in an online fashion. Competing against this strong benchmark often results in pessimistic “tight” guarantees. There has been a recent interest in considering the alternative online benchmark which may allow for better approximation guarantees. In this talk, I will discuss algorithms for the online stochastic weighted matching problem that are designed specifically to compete against the online benchmark.

Based on joint work with Mark Braverman and Antonio Molina Lovett.

—

Speaker: Soheil Behnezhad

Title: Massively Parallel Computation: Recent Advances and Open Problems

Abstract:
The massively parallel computation (MPC) model is a clean theoretical model of successful practical frameworks such as MapReduce, Hadoop, or Spark for processing massive data. In this talk, I will define the model, survey a number of recent results on fundamental graph problems, and mention a few open problems of the area.