Past Events

A lot of well-studied problems in CS Theory are about making “sketches” of graphs that occupy much less space than the graph itself, but where the shortest path distances of

The chromatic number of the Kneser graph (conjectured in 1955) was a seemingly difficult open problem until it was solved by Lovasz in 1978 by using quite non-trivial ideas from

Probability theory rests on seemingly firm axioms, yet simple questions continue to confound philosophers and intrigue the public. We'll examine some of these questions and try to determine whether they

This presentation describes joint work with Ian Mertz and Yuanhao Wei

The sensitivity conjecture is one of the core unresolved questions of computational complexity. In this talk, I will look at one angle that has been taken in tackling this problem,

http://dimacs.rutgers.edu/archive/Events/2017/abstracts/Skokan_Abstract.pdf

A Cubeline means a geodesic on the cube surface. What can we say about the equidistribution of a concrete Cubeline with given slope, say slope square-root-2? What about the equidistribution

We will look at some bijective proofs of partition identities.

In this talk, we will look at decoding Reed-Muller codes beyond their minimum distance when the errors are random (i.e., in the binary symmetric channel). A recent beautiful result of

Random to random is a card shuffling model that was created to study strong stationary times. Although the mixing time of random to random has been known to be of

A well known example of an incidence theorem is Pappus' Hexagon Theorem that: If the six vertices of a hexagon lie alternately on two straight lines, then the three intersection

Greedy algorithms are great when they work. They are often very fast and simple to implement. For many problems, though, it it can be misleading, sometimes giving a really far

We prove the first super-logarithmic lower bounds on the cell-probe complexity of dynamic *boolean* (a.k.a. decision) data structure problems, a long-standing milestone in data structure lower bounds. We introduce a

The celebrated hook-length formula of Frame, Robinson and Thrall from 1954 gives a product formula for the number of standard Young tableaux of straight shape. No such product formula exists

Given a logical formula in n Boolean variables, how can we determine whether there is an assignment to the variables that makes it true? This is the task of Boolean

How many convex quadrilaterals must occur among n points in the plane, no three of which are collinear? We will consider this question in a few small cases, and see

Multilinear maps are known to have numerous applications to cryptography. Unfortunately, current proposals for multilinear maps suffer from major security vulnerabilities due to a class of attacks known as “zeroizing”

We are concerned with the following Ramsey-type question: if the edges of a graph G are r-colored (not necessarily properly), what is the largest monochromatic component (or path, or cycle)

At the beginning of the 20th century, G.D. Birkhoff called the N body problem of celestial mechanics the most celebrated problem in mathematics. Although this perspective has changed after an