Past Events

DATA INSPIRE an NSF TRIPODS Institute housed in DIMACS is premised on the belief that advances in data science principles are needed to impact the emerging paradigm of intelligent machines and their convergence with human society Part of this effort requires the development of theory and algorithms that can provide

1. The unreliability of the Euclidean distance in high-dimension, making a proximity query meaningless and unstable because there is poor discrimination between the nearest and furthest neighbor [3], see also

The adaptive complexity model was recently introduced in the context of submodular optimization to quantify the information theoretic complexity of black-box optimization in a parallel computation model. Informally, the adaptivity

A "tile" in the space B^n of bit vectors of length n, is a subset S of B^n, such that there is another subset A of B^n so that every

Consider a dynamic graph G = (V, E) that is undergoing a sequence of edge insertions/deletions. We want to design an algorithm that maintains an (approximately) maximum matching in this

We present an explicit formula for the generating function for the number of permutations of length $n$ that avoid 1324 in terms of generating functions for permutations that have a

A distance oracle of a graph is a preferably compact data structure that can efficiently answer queries for the shortest path distance from one query vertex to another. A trivial

The question in the title is deceptively simple, as the answers tend to be the number of certain trees, lattice paths, Young tableaux, and other friendly combinatorial objects. However, the

In this talk, I'll discuss our new approximation algorithms for the dynamic variant of the longest increasing subsequence (LIS) problem. In this setting, operations of the following form arrive sequentially:

We consider a tic-tac-toe-style game on the vertices of the n-dimensional Boolean hypercube {0,1}n with k-dimensional subcubes as winning sets. We describe a pairing strategy that allows the second player

This talk consists of two parts. In the first part, I will review some basic idea of self-normalization (SN) for inference of time series in the context of confidence interval

There are only two sub-quadratic approximation algorithms known for directed diameter: a linear time 2 approximation and a O(n^3/2) time 3/2 approximation. Only the latter is proved to be optimal:

The Rogers-Ramanujan identities are a pair of deep partition identities that were first proven by Rogers in 1894 and (independently) Ramanujan in 1917. In the following years, a variety of

We present proofs of these conjectures, and time permitting, a few other ones.

The coloring problem (i.e., computing the chromatic number of a graph) can be solved in O*(2^n) time, as shown by Björklund, Husfeldt and Koivisto in 2009. For k=3,4, better algorithms

The paper to be presented is: Title: First-Choice Maximal and First-Choice Stable School Choice Mechanisms Authors: Umut Dur, Timo Mennle, Sven Seuken Paper Abstract: We investigate the class of school

Many time varying systems in science are traditionally modeled by ordinary differential equations (ODE). However, for multi-scale systems, where the variables and parameters are typically numerous and poorly measured, it

Flow polytopes are an important class of polytopes in combinatorics whose lattice points and volumes have interesting properties and relations. The Chan-Robbins-Yuen (CRY) polytope is a flow polytope with normalized

A maximum constraint satisfaction problem, Max-CSP(F), is specified by a finite family of constraints F. An instance of the problem on \`n’ variables is given by \`m’ constraints, each applied