We study the complexity of the following algorithmic problem: Given a Boolean function $f$ and a finite set of Boolean functions $B$, decide if there is a circuit with basis $B$ that computes $f$. We show that if both $f$ and all functions in $B$ are given by their truth-table, ... more >>>

The complexity of the Black-White Pebbling Game has remained an open problem for 30 years. It was devised to capture the power of non-deterministic space bounded computation. Since then it has been continuously studied and applied to problems in diverse areas of computer science including VLSI design and more recently ... more >>>

Motivated by the study of Parallel Repetition and also by the Unique
Games Conjecture, we investigate the value of the ``Odd Cycle Games''
under parallel repetition. Using tools from discrete harmonic
analysis, we show that after $d$ rounds on the cycle of length $m$,
the value of the game is ... more >>>