Computer Science and Discrete Mathematics (CSDM)

The EKR theorem, which is the cornerstone of extremal combinatorics, characterizes maximal intersecting families of sets. Its setting fixes a ground set of size n, and then studies the size and structure of intersecting families of subsets of fixed...

We consider the following question: how many points with bounded norm can a "non-degenerate" lattice have. Here, by a "non-degenerate" lattice, we mean an n-dimensional lattice with no surprisingly dense lower-dimensional sublattices.

Dadush and...

Polynomial optimization over hypercubes has important applications in combinatorial optimization. We develop a symmetry-reduction method that finds sums of squares certificates for non-negative symmetric polynomials over k-subset hypercubes that...

In this talk, we consider the problem of explicitly constructing a binary tree code with constant distance and constant alphabet size. We present an explicit binary tree code with constant distance and alphabet size polylog(n), where n is the depth...

We prove that if every problem in NP has n^k-size circuits for a fixed constant k, then for every NP-verifier and every yes-instance x of length n for that verifier, the verifier's search space has a witness for x that can be encoded with a circuit...

We propose a new second-order method for geodesically convex optimization on the natural hyperbolic metric over positive definite matrices. We apply it to solve the operator scaling problem in time polynomial in the input size and logarithmic in the...

We propose a new second-order method for geodesically convex optimization on the natural hyperbolic metric over positive definite matrices. We apply it to solve the operator scaling problem in time polynomial in the input size and logarithmic in the...

Let F be a family of subsets over a domain X that is closed under taking intersections. Such structures are abundant in various fields of mathematics such as topology, algebra, analysis, and more. In this talk we will view these objects through the...

Boolean function analysis traditionally studies Boolean functions on the Boolean cube, using Fourier analysis on the group Z_2^n. Other domains of interest include the biased Boolean cube, other abelian groups, and Gaussian space. In all cases, the...

Boolean function analysis traditionally studies Boolean functions on the Boolean cube, using Fourier analysis on the group Z_2^n. Other domains of interest include the biased Boolean cube, other abelian groups, and Gaussian space. In all cases, the...