Computer Science and Discrete Mathematics (CSDM)

We prove nearly quadratic (in the dimension) lower bounds for randomized algorithms for two basic problems: linear optimization and uniform sampling over convex bodies in the membership oracle model (a convex body K is specified by a point in K, the...

We study the online calibration of multidimensional forecasts over an arbitrary convex set. For forecasting over the hypercube, we give the first algorithm that achieves ε-calibration in a number of rounds polynomial in the dimension, exponentially...

A cornerstone result in complexity theory is that O(1)-depth circuits with unbounded fan-in AND/OR gates computing the parity of an n bit string must have exp(n) size. Two completely different proofs of this are known, both dating back to the 1980's...

Given a hypergraph with edges of size at most 3, the 3-set cover problem asks to determine the minimum size of a family of edges that covers the vertex set. As the problem is NP-hard, it is natural to consider its fractional (linear programming)...

Since their inception, random graphs have been a central topic in probability and combinatorics, offering a remarkably rich landscape for studying how complex structures emerge from randomness. We will discuss the following fundamental questions...

The van der Waerden number w(k;r) is the minimum positive integer N such that every r-coloring of the positive integers up to N contains a monochromatic k-term arithmetic progression. Estimating these numbers has remained a challenging open problem...

The first construction of Ramanujan graphs is due to Lubotzky, Phillips, and Sarnak (STOC 1986, Combinatorica 1987). Their construction and analysis were deeply algebraic, and at the time it seemed that only algebraic methods were strong enough to...

The random geometric graph Geo_d(n,p) is a probability distribution over graphs, constructed by placing n points uniformly on a d-dimensional sphere and connecting two points whenever they are sufficiently close — where the proximity threshold is...

By combining sparse graphs with local constraints, expander codes offer a powerful framework for achieving fast decoding algorithms while maintaining asymptotically good rate and minimum distance. However, the standard constraint-counting arguments...

In the noisy $k$-XOR problem, one is given $y \in \bF_2^\constraints$ and must distinguish between $y$ uniform and $y = A x + e$, where $A$ is the adjacency matrix of a $k$-left-regular bipartite graph with variables and constraints, $x\in \bF_2^...