Computer Science and Discrete Mathematics (CSDM)

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...

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. The syntactic/algebraic approach of "flag...