Computer Science and Discrete Mathematics (CSDM)

Any non-negative univariate polynomial over the reals can be written as a sum of squares.  This gives a simple-to-verify certificate of non-negativity of the polynomial. Rooted in Hilbert's 17th problem, there's now more than a century's work that...

In distributed certification, our goal is to certify that a network has a certain desired property, e.g., the network is connected, or the internal states of its nodes encode a valid spanning tree of the network. To this end, a prover generates...

In this talk, we will show that the supremum of any centered Gaussian process can be approximated to any arbitrary accuracy by a finite dimensional Gaussian process where the dimension of the approximator is just dependent on the target error. As a...

Edit distance is a similarity measure for strings that counts how many characters have to be deleted, inserted or substituted in one string to get another one. It has many applications from comparing DNA sequences to text processing. We are still in...

Where are the hard problems? In the absence of a proof of P ≠ NP, researchers have spent years proving unconditional lower bounds for constrained models of computation. In time, a distinct theme arose: random problems (in particular random...

Given two univariate polynomials, how does one compute their greatest common divisor (GCD)? This problem can be solved in polynomial time using the Euclidean algorithm, and even in quasi-linear time using a fast variant of the Euclidean algorithm...

Over the last two decades we have developed good understanding how to quantify the impact of strategic user behavior on outcomes in many games (including traffic routing and online auctions) and showed that the resulting bounds extend to repeated...

I will discuss recent progress on approximating the metric traveling salesperson problem, focusing on a line of work beginning in 2011 that studies the behavior of the max entropy algorithm. This algorithm is a randomized variant of the beautiful...

Consider the process where a signal propagates downward an infinite rooted tree. On every edge some independent noise is applied to the signal. The reconstruction problem asks whether it is possible to reconstruct the original signal given...

Consider an oracle which takes a point x

and returns the minimizer of a convex function f in an ℓ2

ball of radius r around x. While it is straightforward to show that ≈r−1 queries to this oracle suffice to minimize f

to high accuracy in a unit ball...