Past Events

In this talk, we consider randomized query complexity in the low-error regime, along with the direct sum problem for randomized query complexity. First, we give a total function whose eps-error

Few branches of mathematics have been more influential in the social sciences than game theory. In recent years, it has become an essential tool for all social scientists studying the

We will study a more general notion of Graph Coloring in which the set of permitted colors is different for each vertex, as long as at least {k} colors are

In the graph steaming model, the edges of an n-vertex graph are presented one by one in an arbitrary order and the algorithms can make one or a small number

The event will take place 2 00 5 00 PM in the DIMACS seminar room CoRE 431 Abstract About hundred years ago answering a question of Riemann Steinitz proved the following result Let B be the unit ball of the Euclidean norm in R d and assume that V is

Given a convex cone C in R^d, an integral zonotope T is the sum of segments [0,v_i] (i=1, ... ,m) where each v_i \in C is a vector with integer

In this lecture, in memory of Gert Almkvist (1934-2018), I will describe some fascinating connections he found between a family of series for 1/pi^2 and Calabi-Yau theory.

The prominent approach for analyzing optimization in deep learning is based on the geometry of loss landscapes. While this approach has led to successful treatments of shallow (two layer) networks,

When expanding a product of orthogonal polynomials in the basis of orthogonal polynomials, the coefficients that occur often have a combinatorial interpretation as certain types of partial matchings between finite

Shamir's Problem (circa 1980) asks: for fixed r at least 3 and n a (large) multiple of r, how large should M be so that M random r-subsets of {1,

I will describe the ideas underlying the program CONJECTURING which can be used to make conjectures about upper or lower bounds of invariants (or necessary or sufficient conditions for properties)

I will introduce an isoperimetric inequality for the Hamming cube and some of its applications. The applications include a "stability" version of Harper's edge-isoperimetric inequality, which was first proved by

Population recovery is the problem of learning an unknown distribution over an unknown set of n-bit strings, given access to independent draws from the distribution that have been corrupted according

Groundbreaking results from the 1980s showed the surprising result that any function can be securely computed by a group of participants in a distributed fashion such that each party learns its intended output and nothing more These celebrated results were viewed as theoretical proofs of concept Starting with the FairPlay

The short answer to the second question of the title is: "It is NOT a number". For a longer answer, and for an answer to the first question, come to

We are pleased to announce that NJIT has formally become a DIMACS affiliate partner institution To celebrate this occasion NJIT will host a joint DIMACS NJIT Mixer to introduce new DIMACS members from NJIT to the rest of the DIMACS community At the same time the event will give the

Cayley's formula states that the number of labeled spanning trees of K_n is n^{n-2}. How many of those spanning trees contain a fixed forest? Can you generate a uniformly random

We answer a 1982 conjecture of Erdős and Simonovits about the growth of number of k-walks in a graph, which incidentally was studied even earlier by Blakley and and Dixon

I will talk about a polynomial-time algorithm that decides whether a graph contains an induced cycle of odd length k > 3. Joint work with Maria Chudnovsky, Alex Scott, and