Computer Science and Discrete Mathematics (CSDM)

The algorithm indicated in the title builds on Luks's classical framework and introduces new group theoretic and combinatorial tools. In the first talk we outline the algorithm and state the core group theoretic and algorithmic ingredients. Some of...

I want to sketch some algebraic and geometric tools to solve a variety of extremal problems surrounding Minkowski sums of polytopes and colorful simplicial depth.

We study the two-party communication complexity of the geometric problem of finding an approximate Brouwer fixed-point of a composition of two Lipschitz functions $g \circ f$, where Alice knows $f$ and Bob knows $g$. We prove an essentially tight...

While this lecture is a continuation of the lecture from last Tuesday, I will make it self contained. The main object of study of this talk are matrices whose entries are linear forms in a set of formal variables (over some field). The main problem...

The main object of study of this talk are matrices whose entries are linear forms in a set of formal variables (over some field). The main problem is determining if a given such matrix is invertible or singular (over the appropriate field of...

We show that the bipartite perfect matching problem is in $\textrm{quasi-}\textsf{NC}^2$. That is, it has uniform circuits of quasi-polynomial size and $O(\log^2 n)$ depth. Previously, only an exponential upper bound was known on the size of such...

We will continue Monday's talk on constant-round interactive proofs, going into more details of the full construction and its proof. We will also briefly recap Monday's talk so that it will be beneficial to those who cannot attend on Monday.

Interactive proofs have had a dramatic impact on Complexity Theory and Cryptography. In particular, the celebrated IP=PSPACE Theorem [LFKN92,Shamir92] allows an all-powerful but untrusted prover to convince a polynomial-time verifier of the validity...

I will survey some characterization results on random walks which stick to a small region unusually long. In application we give a description of unitary matrices of large permanent.

One of the major challenges of the research in circuit complexity is proving super-polynomial lower bounds for de-Morgan formulas. Karchmer, Raz, and Wigderson suggested to approach this problem by proving that formula complexity behaves "as...