Computer Science and Discrete Mathematics (CSDM)

The online discrepancy minimization problem asks, given unit vectors v_1, ..., v_t arriving one at a time, for online signs x_1 ..., x_t4 in {-1, 1} so that the signed sum x_1 v_1 + ... + x_t v_t has small coordinates in absolute value.

In the first...

A function f:𝔽n2→𝔽n2 is linear if f(x+y)=f(x)+f(y) for all pairs (x,y).

Suppose f is "a bit linear" -- say, f(x+y)=f(x)+f(y) for 1% of pairs(x,y).  Must f agree with a truly linear function a positive proportion of the time?  How large a proportion...

A recent line of work has shown a surprising connection between multicalibration, a multi-group fairness notion, and omniprediction, a learning paradigm that provides simultaneous loss minimization guarantees for a large family of loss functions...

Coboundary expansion and cosystolic expansion are generalizations of edge expansion to hypergraphs. In this talk, we will first explain how the generalizations work. Next we will motivate the study of such hypergraphs by looking at their...

One of the major open problems in complexity theory is proving super-logarithmic lower bounds on the depth of circuits. Karchmer, Raz, and Wigderson (Computational Complexity 5(3/4), 1995) suggested approaching this problem by proving that depth...

A weighted pseudorandom generator (WPRG) is a generalization of a pseudorandom generator (PRG) in which, roughly speaking, probabilities are replaced with weights that are permitted to be positive or negative. In this talk, we present new explicit...

Is randomness ever necessary for space-efficient computation? It is commonly conjectured that L = BPL, meaning that halting decision algorithms can always be derandomized without increasing their space complexity by more than a constant factor. In...

Consider a function on Rn that can be written as a sum of functions f=f1 + f2 + ... + fm, for m greater than n.

The question of approximating f by a reweighted sum using only a small number of summands has many applications in CS theory, mathematical...

Strong spatial mixing (SSM) is an important and widely studied quantitative notion of "correlation decay" for a variety of natural distributions arising in statistical physics, probability theory, and theoretical computer science. One of the most...

Explicit constructions of "random-like" objects play an important role in complexity theory and pseudorandomness. For many important objects such as prime numbers and rigid matrices, it remains elusive to find fast deterministic algorithms for...