dimacs logo color

Events

Past Events

Nov 29 2017

What We Have Here is a Failure to Communicate: A Communication Game and Applications to the Sensitivity Conjecture

Information
Wednesday, November 29, 2017
12:10 PM - 1:00 PM
Type: Seminars | Graduate Combinatorics Seminar
Presenter(s): John Chiarelli - Rutgers University
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,
Nov 27 2017

The Multicolour Ramsey Number of a Long Odd Cycle

Information
Monday, November 27, 2017
2:00 PM - 3:00 PM
Type: Seminars | Rutgers Discrete Mathematics Seminar
Presenter(s): Jozsef Skokan - London School of Economics
http://dimacs.rutgers.edu/archive/Events/2017/abstracts/Skokan_Abstract.pdf
Nov 20 2017

Combinatorics and equidistribution of geodesics on flat surfaces

Information
Monday, November 20, 2017
2:00 PM - 3:00 PM
Type: Seminars | Rutgers Discrete Mathematics Seminar
Presenter(s): Jozsef Beck - Rutgers University
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
Nov 16 2017

Remarks on the Classification of the Finite Simple Groups

Information
Thursday, November 16, 2017
5:00 PM - 6:00 PM
Type: Seminars | Experimental Math Seminar
Presenter(s): Richard Lyons - Rutgers University
Nov 15 2017

Partition Bijections

Information
Wednesday, November 15, 2017
12:10 PM - 1:00 PM
Type: Seminars | Graduate Combinatorics Seminar
Presenter(s): Matthew Russell - Rutgers University
We will look at some bijective proofs of partition identities.
Nov 15 2017

Syndrome Decoding of Reed-Muller Codes and Tensor Decomposition over Finite Fields

Information
Wednesday, November 15, 2017
11:00 AM - 12:00 PM
Type: Seminars | Theoretical Computer Science Seminar
Presenter(s): Aditya Potukuchi - Rutgers University
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
Nov 13 2017

Cutoff for Random to Random

Information
Monday, November 13, 2017
2:00 PM - 3:00 PM
Type: Seminars | Rutgers Discrete Mathematics Seminar
Presenter(s): Evita Nestoridi - Princeton University
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
Nov 09 2017

Computer Generation of Incidence Theorems in Projective Geometry

Information
Thursday, November 9, 2017
5:00 PM - 6:00 PM
Type: Seminars | Experimental Math Seminar
Presenter(s): Alexander Ryba - Queens College, City University of New York
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
Nov 08 2017

Matroids and Greedy Algorithms

Information
Wednesday, November 8, 2017
12:10 PM - 1:00 PM
Type: Seminars | Graduate Combinatorics Seminar
Presenter(s): Andrew Lohr - Rutgers University
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
Nov 08 2017

Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds

Information
Wednesday, November 8, 2017
11:00 AM - 12:00 PM
Type: Seminars | Theoretical Computer Science Seminar
Presenter(s): Omri Weinstein - Columbia University
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
Nov 06 2017

Hook formulas for skew shapes: combinatorics, asymptotics and beyond

Information
Monday, November 6, 2017
2:00 PM - 3:00 PM
Type: Seminars | Rutgers Discrete Mathematics Seminar
Presenter(s): Greta Panova - University of Pennsylvania
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
Nov 02 2017

Boolean Satisfiability

Information
Thursday, November 2, 2017
5:00 PM - 6:00 PM
Type: Seminars | Experimental Math Seminar
Presenter(s): Anthony Zaleski - Rutgers University
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
Nov 01 2017

Counting Convex Quadrilaterals

Information
Wednesday, November 1, 2017
12:10 PM - 1:00 PM
Type: Seminars | Graduate Combinatorics Seminar
Presenter(s): George Hauser - Rutgers University
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
Nov 01 2017

The MMap Strikes Back: Conquering Cryptography using Weak Multilinear Maps

Information
Wednesday, November 1, 2017
11:00 AM - 12:00 PM
Type: Seminars | Theoretical Computer Science Seminar
Presenter(s): Mark Zhandry - Princeton University
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”
Oct 30 2017

Monochromatic Components in Random Graphs

Information
Monday, October 30, 2017
2:00 PM - 3:00 PM
Type: Seminars | Rutgers Discrete Mathematics Seminar
Presenter(s): Deepak Bal - Montclair State University
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)
Oct 26 2017

Problems in Celestial Mechanics

Information
Thursday, October 26, 2017
5:00 PM - 6:00 PM
Type: Seminars | Experimental Math Seminar
Presenter(s): Harry Gingold - West Virginia University
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
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