ACO Student Seminar

Abstract: 

How does the local firing of neurons in the brain translate to perception, memory, and decision making? This talk will survey neural population models that tackle this question through the lens of dynamical systems. I will focus on two core phenomena --- decision making via competition and memory via attractor dynamics --- and highlight both classical results and recent developments in the field. Beyond their neuroscientific motivation, these models exhibit mathematical structure analogous to varied problems in applied mathematics.

Abstract: 

We study the SIRS process on sparse random graphs with power--law degree distributions.

A large physics literature reports numerical evidence for a positive epidemic threshold for SIRS with waning immunity on scale--free networks, suggesting a transition between short--lived and exponentially long--lived regimes.

In contrast, for the SIS/contact process on power--law graphs with exponent $\tau>3$, it is rigorously known that the critical value is $\lambda_c=0$ and that survival is exponentially long for every $\lambda>0$.

We show that, in a survival--time sense, the true threshold for SIRS on power--law random graphs with $\tau>3$ is also zero. Joint work with Debankur Mukherjee and Souvik Dhara. 

Abstract: 

 I will discuss the problem of finding confidence sets for arbitrary distributions.  This is a fundamental statistical task with connections to many problems, like support estimation, robust estimation, and conformal prediction.  Given samples from a distribution D, the goal is to find a small set that contains at least a target 1 - \alpha probability mass of D. We study this in a setup similar to PAC learning, where, for a fixed family of sets F, our goal is to find a set that achieves coverage on D, and has volume comparable to the smallest set in F that achieves coverage on D.  

In the first part of the talk, I will discuss some work in the high-dimensional setting, where D is supported on \mathbb{R}^d. We give an efficient algorithm that learns a confidence ellipsoid that has volume approximately that of the smallest-volume confidence ellipsoid of bounded condition number.  

In the second part of the talk, I will discuss an online formulation of the confidence set problem. We show that the problem of learning confidence sets looks quite different from the standard online learning problem. This talk is based on joint work with Chao Gao, Liren Shan, and Aravindan Vijayaraghavan.

Abstract: We revisit a classic topic in probabilistic combinatorics, the lower-tail large-deviation problem for triangles in the random graph $G(n,p)$.  We aim for first-order asymptotics for the quantity $\Pr [ X =k] $ with $X$ the number of triangles in $G(n,p)$ and $0 \le k \le C \E X$.  When $k=0$ (the case of triangle-freeness) first-order asymptotics are known via Janson's Inequality and extensions when $p = p(n)$ is sufficiently small;  when $k$ is sufficiently close to $\E X$ first-order asymptotics are known via local central limit theorems.  Our main result gives first-order asymptotics for all $k$ in the above range when $p = o(n^{-2/3})$, improving upon the result of Frieze that required $p= o(n^{-4/5})$. 

We also characterize the distribution of the $k$ triangles in the corresponding conditional distribution, as well as give an efficient algorithm to sample from the conditional distribution.  

Joint work with Will Perkins

Abstract: 

We establish a spectral gap for Continuum Glauber dynamics on the hard sphere model assuming strong spatial mixing, thereby extending the range of parameters in which Continuum Glauber is provably rapidly mixing. To do this, we introduce continuous extensions of spectral independence and negative fields localization. Our techniques apply to general Gibbs point processes with finite-range repulsive pair potentials. As a corollary, we improve the threshold up to which packings of a fixed number of spheres can be sampled from a bounded domain. Joint work with Aiya Kuchukova and Santosh Vempala. 

Abstract: Given a simple graph on $n$ vertices and a parameter $k$, the triangle-densest-$k$-subgraph problem is known to be computationally hard in the worst case. To circumvent the computational hardness, we study an average-case model where a triangle-dense subgraph on $k$ vertices is planted in an Erd\H{o}s--R\'enyi random graph on $n$ vertices. For the recovery of the planted subgraph, we propose a simple spectral algorithm and a semidefinite program, both of which use a graph matrix whose entries are local signed triangle counts. Theoretical guarantees for these algorithms are established through spectral analysis of the graph matrix. Finally, we provide evidence showing a statistical-to-computational gap analogous to that for the planted clique problem. The computational threshold in terms of the subgraph size $k$ is at least $\sqrt{n}$ in the framework of low-degree polynomial algorithms, while the information-theoretic threshold is at most logarithmic in $n$. Joint work with Cheng Mao and Benjamin McKenna.

Abstract: Locally decodable codes (LDCs) allow you to recover any bit of a message by reading only a few bits of its encoding, even if the encoding has been partially corrupted. They're beautiful objects with connections across TCS, but they come with a catch: all known constructions with constant query complexity have enormous (superpolynomial) length.

In 2004, Ben-Sasson et al. introduced a natural relaxation: let the decoder say "I don't know" when it detects corruption. This modest change turns out to be surprisingly powerful. It allows for constant-query codes with nearly-linear length. But is this construction optimal? The question has remained open for twenty years.

We prove a nearly matching lower bound, resolving the complexity of linear relaxed LDCs up to constants in the exponent. The heart of our proof is a new combinatorial object we call a robust daisy, a relaxed cousin of the robust sunflower. While robust sunflowers are rare structures that only emerge in very large set systems, we show that every distribution over small sets contains a dense robust daisy. This abundance is exactly what makes them useful for proving lower bounds. Joint work with Guy Goldberg and Tom Gur. 

Enjoy Spring Break!

Abstract: Suppose there is a ground set of n points lying in a 1-dimensional space, we want to box as many points as possible while minimizing the cost (size of the box). In this case the cost function is close to but not submodular, which makes the function harder to analyze. We show that the convex hull of the epigraph of the function under non-negative constraint can still be obtained by exploiting the combinatorial structure of the function.

This is a joint work with Santanu Dey, Oktay Gunluk, and Jisun Lee.

Abstract: In online welfare maximization, a sequence of n players arrive one by one and sample valuations over m resources from known probability distributions. Upon seeing the realization of a player's valuation, we must immediately and irrevocably decide how much of each item to allocate, while maximizing the expected sum of player valuations. There is a long line of work studying this problem in the setting of indivisible items with combinatorial valuations. In particular, we know good approximation algorithms against both the prophet/offline benchmark and against the philosopher/online benchmark. In this work, we study online welfare maximization for divisible items.

We provide approximation algorithms for this problem for concave diminishing returns valuations for both the offline and online benchmarks. When compared to the prophet/offline optimum, we prove that there is a 1/2-competitive algorithm and that this factor is tight. When compared to the philosopher/online optimum, we provide a (1-1/e)-competitive algorithm. Our online algorithm relies on a reduction to a single item online contention resolution (OCRS) with upper bounds and the construction of such an OCRS scheme. On the hardness side, we show that computing the optimal online policy for the philosopher benchmark is #P-hard.

Joint work with Mohit Singh and Sahil Singla.

Abstract: In the classic online graph balancing problem, edges arrive sequentially and must be oriented

immediately upon arrival, to minimize the maximum in-degree. For adversarial arrivals, the

natural greedy algorithm is O(logn)-competitive, and this bound is the best possible for any

algorithm, even with randomization. We study this problem in the i.i.d. model where a base

graph G is known in advance and each arrival is an independent uniformly random edge of G.

This model generalizes the standard power-of-two choices setting, corresponding to G = Kn,

where the greedy algorithm achieves an O(loglogn) guarantee. We ask whether a similar bound

is possible for arbitrary base graphs.

While the greedy algorithm is optimal for adversarial arrivals and also for i.i.d. arrivals from

regular base graphs (such as G = Kn), we show that it can perform poorly in general: there exist

mildly irregular graphs G for which greedy is Ω(logn)-competitive under i.i.d. arrivals. In sharp

contrast, our main result is an O(loglogn)-competitive online algorithm for every base graph G;

this is optimal up to constant factors, since an Ω(loglogn) lower bound already holds even for

the complete graph G = Kn. The key new idea is a notion of log-skewness for graphs, which

captures the irregular substructures in G that force the offline optimum to be large. Moreover,

we show that any base graph can be decomposed into “skew-biregular” pieces at only O(loglogn)

scales of log-skewness, and use this to design a decomposition-based variant of greedy that is

O(loglogn)-competitive.

Joint work with Nikhil Bansal, Milind Prabhu, Sahil Singla.

Abstract: We give dynamic algorithms for maintaining the vertex set of a maximum matching of a graph, or a largest nonsingular submatrix of a matrix, in $O(n^{1.405})$ per edge or entry update, via a reduction to dynamic matrix inverse. Prior dynamic algorithms were able to maintain the size of these objects in this time, but not the objects themselves.

Based on joint work with Jan van den Brand and Vishal Kumar.