dimacs logo color

Events

Past Events

Oct 27 2021

Finite Axioms of Choice

Information
Wednesday, October 27, 2021
3:00 PM - 4:00 PM
Type: Seminars | Graduate Combinatorics Seminar
Presenter(s): Brian Pinsky - Rutgers University
The axiom of choice says "every set of non-empty sets has a choice function". This has some well known, slightly problematic consequences. However, abandoning AC can result in much much
Oct 25 2021

Localization and Concentration of Measures on the Discrete Hypercube with Applications to Interacting Particle Systems

Information
Monday, October 25, 2021
2:00 PM - 3:00 PM
Type: Seminars | Rutgers Discrete Mathematics Seminar
Presenter(s): Ronen Eldan - Weizmann Institute of Science
For a probability measure $\mu$ on the discrete hypercube, we are interested in finding sufficient conditions under which $\mu$ either (a) Exhibits concentration (either in the sense of Lipschitz functions,
Oct 21 2021

Combinatorics behind the Degenerate Eulerian Numbers

Information
Thursday, October 21, 2021
5:00 PM - 6:00 PM
Type: Seminars | Experimental Math Seminar
Presenter(s): Orli Herscovici - Georgia Institute of Technology
Works of Carlitz gave an inspiration to many researchers to develop different generalizations of the Eulerian polynomials and numbers. Many of those generalizations have a pure analytical character. It is
Oct 20 2021

Lower Bounds for Shortcut Sets and Additive Spanners

Information
Wednesday, October 20, 2021
11:00 AM - 12:00 PM
Type: Seminars | Theoretical Computer Science Seminar
Presenter(s): Nicole Wein - DIMACS
There are many graph problems of the following form: Given a graph G, construct a graph H that preserves some information about G, while optimizing some property of H. Some
Oct 18 2021

Long Common Subsequences between Bitstrings

Information
Monday, October 18, 2021
2:00 PM - 3:00 PM
Type: Seminars | Rutgers Discrete Mathematics Seminar
Presenter(s): Xiaoyu He - Princeton University
A binary code of positive rate is a subset of {0,1}^n with size exponentially large in n. In any binary code of positive rate, one can find twocodewords sharing the
Oct 15 2021

Locality in Computation

Information
Friday, October 15, 2021
4:00 PM - 5:00 PM
Type: Seminars | DATA-INSPIRE TRIPODS Seminars
Presenter(s): Ronitt Rubinfeld - Massachusetts Institute of Technology
Consider a setting in which inputs to and outputs from a computational problem are so large, that there is not time to read them in their entirety. However, if one
Oct 14 2021

Moments of Permutation Statistics and Central Limit Theorems

Information
Thursday, October 14, 2021
5:00 PM - 6:00 PM
Type: Seminars | Experimental Math Seminar
Presenter(s): Stoyan Dimitrov - University of Illinois, Chicago
We show that if a permutation statistic can be written as a linear combination of bivincular patterns, then its moments can be expressed as a linear combination of factorials with
Oct 13 2021

Time-Optimal Sublinear Algorithms for Matching and Vertex Cover

Information
Wednesday, October 13, 2021
11:00 AM - 12:00 PM
Type: Seminars | Theoretical Computer Science Seminar
Presenter(s): Soheil Behnezhad - Northeastern University
Over the past two decades there has been a growing interest in estimating various graph parameters, such as the size of maximum matching (MM) and minimum vertex cover (MVC), in
Oct 11 2021

Palette Sparsification for Vertex Coloring

Information
Monday, October 11, 2021
2:00 PM - 3:00 PM
Type: Seminars | Rutgers Discrete Mathematics Seminar
Presenter(s): Sepehr Assadi - Princeton University
We prove that for every graph with maximum degree Delta, if we sample O(log n) colors independently and uniformly at random for each vertex from colors {1,...,Delta+1}, then with high
Oct 07 2021

A Dynamic Approach for the Zeros of the Riemann Zeta Function - Collision and Repulsion

Information
Thursday, October 7, 2021
5:00 PM - 6:00 PM
Type: Seminars | Experimental Math Seminar
Presenter(s): Yochay Jerby - Holon Institute of Technology, Israel
The Riemann hypothesis is a question regarding the solutions of the transcendental equation ζ(s)=0, that is the zeros of the Riemann zeta function. The starting point of our talk is
Oct 06 2021

Hardness for Structured Linear Equations and Linear Programs

Information
Wednesday, October 6, 2021
11:00 AM - 12:00 PM
Type: Seminars | Theoretical Computer Science Seminar
Presenter(s): Peng Zhang - Rutgers University
We study structured systems of linear equations (or linear systems) and structured linear programs, commonly arising from combinatorial optimization, operations research, and so on. Many of them can be solved
Oct 06 2021

The Real Reasons Linear Algebra is Useful or: A Love Letter to Traditionalists

Information
Wednesday, October 6, 2021
3:00 PM - 4:00 PM
Type: Seminars | Graduate Combinatorics Seminar
Presenter(s): Robert Dougherty Bliss - Rutgers University
The divide between traditional and experimental combinatorialists is at a breaking point. In a recent talk, it was claimed that linear algebra is useful because of set systems and discrete
Oct 04 2021

A Topological Turán Problem

Information
Monday, October 4, 2021
2:00 PM - 3:00 PM
Type: Seminars | Rutgers Discrete Mathematics Seminar
Presenter(s): Corrine Yap - Rutgers University
The classical Turán problem asks: given a graph H, how many edges can an n-vertex graph have while containing no isomorphic copy of H? By viewing (k+1)-uniform hypergraphs as k-dimensional
Oct 01 2021

Attractors of Nonsmooth and Multivalued Dynamical Systems

Information
Friday, October 1, 2021
10:00 AM - 11:00 AM
Type: Seminars | DATA-INSPIRE TRIPODS Seminars
Presenter(s): Cameron Thieme - DIMACS
Over the past few decades, piecewise-continuous differential equations have become increasingly popular in scientific models. In particular, conceptual climate models often take this form. These nonsmooth systems are typically reframed
Sep 30 2021

An Experimental (yet fully rigorous!) Study of a certain "Measure Of Disarray" that 12-year Noga Alon Proved was always Even

Information
Thursday, September 30, 2021
5:00 PM - 6:00 PM
Type: Seminars | Experimental Math Seminar
Presenter(s): Doron Zeilberger - Rutgers University
In a beautiful new "coffee table book", "Do not Erase", by the very talented artistic photographer Jessica Wynne, there are pictures of more than one hundred blackboards by a very
Sep 29 2021

Hardness vs Randomness, Revised: Uniform, Non-Black-Box, and Instance-Wise

Information
Wednesday, September 29, 2021
11:00 AM - 12:00 PM
Type: Seminars | Theoretical Computer Science Seminar
Presenter(s): Roei Tell - DIMACS
Textbook hardness-to-randomness converts circuit lower bounds into PRGs. But is this black-box approach really necessary for derandomization? In this talk I'll show how to revamp the classical hardness-to-randomness framework, converting
Sep 25 2021

Rutgers Robotics Workshop 2021

Information
Saturday, September 25, 2021 - Saturday, September 25, 2021
9:00 AM - 4:00 PM
Type: Workshops

The workshop is held annually as part of the NSF National Research Traineeship SOCRATES Socially Cognizant Robotics for a Technology Enhanced Society co sponsored by DATA INSPIRE DATA science for INtelligent Systems and People Interaction an NSF TRIPODS Institute based at Rutgers University http robotics cs rutgers edu data inspire

Sep 23 2021

Coloring Subsets with r-wise Intersecting Color Classes

Information
Thursday, September 23, 2021
5:00 PM - 6:00 PM
Type: Seminars | Experimental Math Seminar
Presenter(s): Noga Alon - Princeton University and Tel Aviv University
What is the minimum number of colors required in a coloring of all k-subsets of an n-set so that every color class is r-wise intersecting? We suggest a conjectured answer
Sep 22 2021

Reversing Color Coding

Information
Wednesday, September 22, 2021
11:00 AM - 12:00 PM
Type: Seminars | Theoretical Computer Science Seminar
Presenter(s): Karthik C.S. - Rutgers University
In computational complexity it is often easier to prove hardness results for a colored version of a combinatorial or graph theoretic problem than its uncolored counterpart. Moreover, one can typically
Sep 21 2021

Workshop on Algorithmic Social Choice

Information
Tuesday, September 21, 2021 - Wednesday, September 22, 2021
9:00 AM - 9:00 AM
Type: Workshops
Organizer(s): Ashish Goel
Social choice has a rich history tracing back to the work of Borda Condorcet Laplace and others in the 18th century and the work of Kenneth Arrow in the 1950s that led to the Nobel Prize in Economics A current working definition might say that social choice theory studies how