Computer Science and Discrete Mathematics (CSDM)

The degree mantra states that any non-zero univariate polynomial of degree at most d has at most d roots (counted with multiplicity). A generalization of this to the multivariate setting, proved by Dvir-Kopparty-Saraf-Sudan asserts that over any...

Reproducibility is vital to ensuring scientific conclusions are reliable, but failures of reproducibility have been a major issue in nearly all scientific areas of study in recent decades. A key issue underlying the reproducibility crisis is the...

Consider the action of a group on a finite-dimensional vector space. Given some natural conditions on the group, Hilbert showed a famous "duality" between invariant polynomials and closures of group orbits. Namely, the orbit closure of a vector is...

Expander graphs are sparse and yet well-connected graphs. Several applications in theoretical computer science require explicit constructions of expander graphs, sometimes even with additional structure. One approach to their construction is to...

A binary code is simply any subset of 0/1 strings of a fixed length. Given two strings, a standard way of defining their distance is by counting the number of positions in which they disagree. Roughly speaking, if elements of a code are sufficiently...

The ABNNR encoding is a classical encoding scheme that amplifies the distance of an error correcting code. The encoding takes an error correcting code with a small distance and constructs an error correcting code with distance approaching one, by...

As solutions can be efficiently verified, any NP-complete problem can be solved by exhaustive search. Unfortunately, even for small instances the running time for exhaustive search becomes very high. 

On the bright side, for many NP-complete...

Constraint Satisfaction Problems (CSPs) are among the most well-studied problems in Computer Science, 3SAT being a prominent example.

Let Σ be an alphabet and P:Σk→{0,1} be a fixed predicate. The assignments in P−1(1) are deemed as satisfying...

The field of continuous combinatorics studies large (dense) combinatorial structures by encoding them in a "continuous" limit object, which is amenable to tools from analysis, topology, measure theory, etc. While the syntactic/algebraic approach of...

A Kakeya Set in (Z/N Z)^n is a set that contains a line in every direction.  It has been known for over a decade that such sets must be large when N is prime (or more generally over any finite field).  This goes back to Dvir's proof of the finite...