Computer Science and Discrete Mathematics (CSDM)

In this talk, I will discuss progress on showing hardness of the Minimum Circuit Size Problem (MCSP). The computational complexity of MCSP is a longstanding mystery, dating back as far as Levin's seminal work on NP-completeness in 1973. Over the...

Consider a scenario where we are learning a predictor, whose predictions will be evaluated by their expected loss. What if we do not know the precise loss at the time of learning, beyond some generic properties (like convexity)? What if the same...

The Tree Evaluation Problem has emerged in the past decade as a leading candidate for separating logspace from polynomial time. In this talk we will introduce the problem, as well as the context behind its introduction and conjectured hardness. We...

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...