dimacs logo color

Events

Past Events

Oct 25 2017

Towards Optimal Randomness Extractors and Ramsey Graphs

Information
Wednesday, October 25, 2017
11:00 AM - 12:00 PM
Type: Seminars | Theoretical Computer Science Seminar
Presenter(s): Eshan Chattopadhyay - Institute for Advanced Study
I will survey some of the recent exciting progress on explicit constructions of randomness extractors for independent sources. Many of the new constructions rely on explicit constructions of newly introduced
Oct 23 2017

DIMACS/Northeast Big Data Hub Workshop on Overcoming Barriers to Data Sharing including Privacy and Fairness

Information
Monday, October 23, 2017 - Tuesday, October 24, 2017
8:30 AM - 5:30 PM
Type: Workshops
Organizer(s): Tal Rabin | René Bastón | Rebecca  Wright | Salil Vadhan | Adam Smith | John Abowd

This workshop will bring together computer scientists legal scholars social scientists and consumers of data to understand the extent to which privacy currently limits the sharing of data Discussions will include but not be limited to research data and will seek to develop standards and best practices that enable new

Oct 23 2017

The Structure of Triangle-free Graphs with no Induced Six-vertex Path

Information
Monday, October 23, 2017
2:00 PM - 3:00 PM
Type: Seminars | Rutgers Discrete Mathematics Seminar
Presenter(s): Sophie Spirkl - Princeton University
I will talk about an explicit construction for triangle-free graphs that do not contain a six-vertex path as an induced subgraph. Examples include the 16-vertex Clebsch graph, and the graph
Oct 19 2017

Growing Graceful Trees

Information
Thursday, October 19, 2017
5:00 PM - 6:00 PM
Type: Seminars | Experimental Math Seminar
Presenter(s): Edinah Gnang - Johns Hopkins University
In this talk we will describe and motivate the graceful labeling conjecture. We will discuss enumerative aspects of the conjecture and describe how it serves as a wonderful test case
Oct 18 2017

Fifty Shades of Gray Codes

Information
Wednesday, October 18, 2017
12:10 PM - 1:00 PM
Type: Seminars | Graduate Combinatorics Seminar
Presenter(s): Danny Scheinerman - Rutgers University
We will describe the classical Gray code and some of its nice properties. We can generalize Gray codes as walks generally through a collection of objects where each step the
Oct 18 2017

A Smoothed Analysis of the Greedy Algorithm for the Linear Contextual Bandit Problem

Information
Wednesday, October 18, 2017
11:00 AM - 12:00 PM
Type: Seminars | Theoretical Computer Science Seminar
Presenter(s): Steven Wu - University of Pennsylvania
Bandit learning models the common setting when the decisions of an algorithm feed back into its training data, and it cannot observe counter-factuals. These settings include criminal recidivism prediction (would
Oct 16 2017

Approximate Affine Invariance and Distance to Polynomials

Information
Monday, October 16, 2017
2:00 PM - 3:00 PM
Type: Seminars | Rutgers Discrete Mathematics Seminar
Presenter(s): Swastik Kopparty - Rutgers University
Let F be a finite field, and let V be the set of functions from F to F computed by a univariate polynomial of degree at most d. It is
Oct 12 2017

Wittgenstein versus Gödel

Information
Thursday, October 12, 2017
5:00 PM - 6:00 PM
Type: Seminars | Experimental Math Seminar
Presenter(s): Art DuPre - Rutgers University

Because of a "Notorius" paragraph in Wittgenstein's 'Remarks on the Foundations of Mathematics' and the controversy it caused among mathematicians, logicians and philosophers, Hao Wang, among others, lay this controversy

Oct 11 2017

What do the largest subgraphs of K_n (or the random graph!) with a particular matching number look like?

Information
Wednesday, October 11, 2017
12:10 PM - 1:00 PM
Type: Seminars | Graduate Combinatorics Seminar
Presenter(s): Abigail Raz - Rutgers University
There are many statements across math of the form "a structure with property X must have one of the following forms". We will see a few of these statements focusing
Oct 11 2017

Practical Data-Dependent Metric Compression with Provable Guarantees

Information
Wednesday, October 11, 2017
11:00 AM - 12:00 PM
Type: Seminars | Theoretical Computer Science Seminar
Presenter(s): Ilya Razenshteyn - Columbia University
How well can one compress a dataset of points from a high-dimensional space while preserving pairwise distances? Indyk and Wagner have recently obtained almost optimal bounds for this problem, but
Oct 09 2017

A Reverse Minkowski Theorem

Information
Monday, October 9, 2017
2:00 PM - 3:00 PM
Type: Seminars | Rutgers Discrete Mathematics Seminar
Presenter(s): Noah Stephens-Davidowitz - Princeton University
A classical problem in the geometry of numbers asks us to estimate how many lattice points lie in some ball around the origin. Minkowski's celebrated theorem gives us a tight
Oct 05 2017

Three Lovely Problems from OEIS

Information
Thursday, October 5, 2017
5:00 PM - 6:00 PM
Type: Seminars | Experimental Math Seminar
Presenter(s): Neil Sloane - OEIS Foundation
I'll discuss problems from geometry, number theory, and the theory of computing. Poonen and Rubinstein counted the intersection points in a regular n-gon with all diagonals drawn. But what if
Oct 04 2017

Topological Graph Theory

Information
Wednesday, October 4, 2017
12:10 PM - 1:00 PM
Type: Seminars | Graduate Combinatorics Seminar
Presenter(s): Corrine Yap - Rutgers University
What happens when we take the graphs we know and love and stick them on the torus? What about the Möbius strip? Or the Klein bottle? We'll talk about how
Oct 04 2017

A Computer Scientist Thinks about the Brain

Information
Wednesday, October 4, 2017
11:00 AM - 12:00 PM
Type: Seminars | Theoretical Computer Science Seminar
Presenter(s): Christos Papadimitriou - University of California, Berkeley
When key problems in science are revisited from the computational viewpoint, occasionally unexpected progress results. There is a reason for this: implicit algorithmic processes are present in the great objects
Sep 28 2017

CNF-DNF and All That

Information
Thursday, September 28, 2017
5:00 PM - 6:00 PM
Type: Seminars | Experimental Math Seminar
Presenter(s): Doron Zeilberger - Rutgers University
The acronyms CNF and DNF feature prominently in Norbert Blum's brave attempt at proving the most important open problem of our time (with the possible exception of the much more
Sep 27 2017

Entropy

Information
Wednesday, September 27, 2017
12:10 PM - 1:00 PM
Type: Seminars | Graduate Combinatorics Seminar
Presenter(s): Cole Franks - Rutgers University
Shannon's entropy shows up in many places in mathematics, information theory, and computer science. After an overview of the basic concepts, I will discuss some non-obvious applications of the entropy
Sep 27 2017

On the Quantitative Hardness of CVP

Information
Wednesday, September 27, 2017
11:00 AM - 12:00 PM
Type: Seminars | Theoretical Computer Science Seminar
Presenter(s): Noah Stephens-Davidowitz - Princeton University
For odd integers p >= 1 (and p = infty), we show that the Closest Vector Problem in the ell_p norm (CVP_p) over rank n lattices cannot be solved in
Sep 20 2017

Machine Learning in a Setting of Ordinal Distance Information

Information
Wednesday, September 20, 2017
11:00 AM - 12:00 PM
Type: Seminars | Theoretical Computer Science Seminar
Presenter(s): Matthäus Kleindessner - University of Tübingen
In a typical machine learning scenario we are given numerical dissimilarity values between objects (or feature representations of objects, from which such dissimilarity values can readily be computed). In the
Sep 20 2017

Number of Maximal Independent Sets

Information
Wednesday, September 20, 2017
12:10 PM - 1:00 PM
Type: Seminars | Graduate Combinatorics Seminar
Presenter(s): Jinyoung Park - Rutgers University
For a given graph G, a subset A of V(G) is independent if no two vertices in A are adjacent. Some time ago, Erdos and Moser asked: what’s the maximum
Sep 14 2017

Sporadic Apéry-like Numbers Modulo Primes

Information
Thursday, September 14, 2017
5:00 PM - 6:00 PM
Type: Seminars | Experimental Math Seminar
Presenter(s): Amita Malik - Rutgers University

At the ICM in 1978, R. Apéry's proof of the irrationality of ζ(3) was presented. In this proof, he introduced a sequence of integers, now known as Apéry numbers. Apéry-like