# Computer Science and Discrete Mathematics (CSDM)

## CSDM - On The Complexity of Circuit Satisfiability

We present a gap theorem regarding the complexity of the circuit satisfiability problem.

We prove that the success probability of deciding Circuit Satisfiability for deterministic

circuits with *n* variables and size *m* is either *2 ^{−n}* or

*2*when restricted to probabilistic

^{−o(n)}circuit families

*{C*where the size of C

_{n,m}}_{n,m}is bounded by 2

*.*

^{o(n)}poly(m)## The Completeness of the Permanent

In his seminal work, Valiant defined algebraic analogs for the classes P and NP, which are known today as VP and VNP. He also showed that the permanent is VNP-complete (that is, the permanent is in VNP and any problem in VNP is reducible to it). We will describe the ideas behind the proof of this completeness of the permanent.

## CSDM - The Detectability Lemma and Quantum Gap Amplification

## CSDM - Span Programs and Quantum Query Algorithms

The general adversary bound is a lower bound on the number of input queries required for a quantum algorithm to evaluate a boolean function. We show that this lower bound is in fact tight, up to a logarithmic factor. The proof is based on span programs. It implies that span programs are an (almost) equivalent computational model to quantum query algorithms.

## CSDM - The Completeness of the Permanent

In his seminal work, Valiant defined algebraic analogs for the classes P and NP, which are known today as VP and VNP. He also showed that the permanent is VNP-complete (that is, the permanent is in VNP and any problem in VNP is reducible to it). We will describe the ideas behind the proof of this completeness of the permanent.

## CSDM - Twice-Ramanujan Sparsifiers

We prove that every graph has a spectral sparsifier with a number of edges linear in its

number of vertices. As linear-sized spectral sparsifiers of complete graphs are expanders, our

sparsifiers of arbitrary graphs can be viewed as generalizations of expander graphs.

In particular, we prove that for every d > 1 and every undirected, weighted graph G =

(V,E,w) on n vertices, there exists a weighted graph H = (V, F, ~w) with at most dn edges

such that for every x ∈ ℜ^{V} ,