[July 2017] Is Your Database Secure?: New Attacks and Leaks Discovered
Rutgers computer science graduate student Betül Durak has a growing body of research on encryption methods that provide security guarantees while also satisfying additional practical requirements. She recently helped to uncover an attack on the FF3 encryption method recommended by NIST for securing information in databases, and she showed that secure order-revealing encryption methods can be vulnerable to multi-column attacks on correlated tabular data. >>

[October 2016] Recent Results in Locally Testable and Locally Decodable Codes
IAS/DIMACS postdoctoral fellow Noga Ron-Zewi and her collaborators have made several recent breakthroughs in the study of locally testable and locally decodable codes. Among other things, their work provides an exponential improvement on the best-known query complexity of such codes. >>

[August 2016] On Tuza's Conjecture in Dense Graphs
Rutgers graduate student Jake Baron and his advisor Jeff Kahn have provided a construction that shows that a bound on the size of minimum triangle edge cover of a graph G conjectured by Zsolt Tuza in 1981 is, in fact, asymptotically tight for an infinite family of dense graphs. This disproves a more recent conjecture to the contrary by Raphael Yuster. >>

[May 2015] REU 2014: Research in Review
DIMACS will welcome students participating in the 2015 Research Experiences for Undergraduates (REU) program on June 1, and it looks like the students from the 2014 program left them big shoes to fill. During the past year, the 2014 REU students have co-authored 13 papers, given 13 conference talks, and presented many more posters describing their research. In anticipation of the 2015 program, we highlight a few of the results from the 2014 group. >>

[November 2013] Differentially Private Modeling of Human Mobility at Metropolitan Scales
Former Rutgers graduate student Darakhshan Mir and her collaborators, Rebecca Wright, Ramón Cáceres, Sibren Isaacman, and Margaret Martonosi, developed a new method that applies differential privacy to human mobility modeling in metropolitan areas. The goal of the new work is to realistically model how large populations move within a metropolitan area while rigorously safeguarding the privacy of individuals whose data are used. >>

[October 2012] Discrepancy of Three Permutations
DIMACS researcher Alantha Newman and graduate student Aleksandar Nikolov discovered a counterexample to a long-standing a conjecture by Jozsef Beck (Rutgers) on the discrepancy of a set system arising from three permutations on the integers 1 through n. Given a set system (i.e., m sets on n elements where m is O(n)), the problem is to assign each element a value of 1 or -1 so as to minimize the maximum over all sets of the absolute value of the sum of the values assigned to its elements. This minimum is the discrepancy.   >>

[May 2012] Mantel’s Theorem for Random Graphs
Rutgers graduate student Bobby DeMarco and his advisor Jeffry Kahn (pictured) have determined when the size of the largest triangle-free subgraph and the largest bipartite subgraph of a random graph are likely to be equal. This is the “random graph version” of a classic (1907) result by Mantel showing that the sizes are equal in a complete graph.  >>

DIMACS Home Page