Computer Science and Discrete Mathematics (CSDM)

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

Ramanujan graphs are optimal expander graphs, and their existence and construction have been the focus of much research during the last three decades. We prove that every bipartite Ramanujan graph has a $d$-covering which is also Ramanujan. This...

Let $f$ be a polynomial of degree $d$ in $n$ variables over a finite field $\mathbb{F}$. The polynomial is said to be unbiased if the distribution of $f(x)$ for a uniform input $x \in \mathbb{F}^n$ is close to the uniform distribution over $\mathbb...

Joint work with Oded Goldreich. We prove that random $n$-by-$n$ Toeplitz matrices over $GF(2)$ have rigidity $\Omega(n^3/(r^2 \log n))$ for rank $r > \sqrt{n}$, with high probability. This improves, for $r = o(n / \log n \log\log n)$, over the $...

We will start with presenting the basic notions of (co)homomology of simplical complexes (which requires only basic linear algebra over the field of order 2) and then we will indicate its relevance for several topics in computer science and...

We introduce a method for proving lower bounds on the efficacy of semidefinite programming (SDP) relaxations for combinatorial problems. In particular, we show that the cut, TSP, and stable set polytopes on $n$-vertex graphs are not the linear image...