• Calendar

January 8, Sunday
12:00 – 14:00

I will present a simple randomized construction of size $n^3$ and depth $5.3 \log(n)$ monotone circuit for the majority function on n variables.The result can be viewed as a reduction in the size and a partial derandomization of Valiant's classical construction of an $n^{5.3}$ monotone formula from 1984. On the other hand, compared with the deterministic monotone circuit obtained from the sorting network of Ajtai, Komlos, and Szemeredi 1983, the circuit is much simpler and has depth $O(\log n)$ with a small constant.

Techniques used in the construction incorporate fairly recent results showing that expansion yields performance guarantee for the belief propagation message passing algorithms for decoding low-density parity-check (LDPC) codes. As part of the construction, we obtain optimal-depth linear-size monotone circuits for the promise version of the problem, where the number of 1's in the input is promised to be either less than one third, or greater than two thirds. At last, I will show that the size can be further reduced at the expense of increased depth, and obtain a monotone circuit for the majority of size and depth about $n^{1+sqrt(2)}$ and $9.9log(n)$.

Joint work with Avner Magen and Toni Pitassi.

Short Bio:

I am a postdoc in the theory group at the Department of Computer Science in the University of British Columbia and at the Pacific Institute for the Mathematical Sciences. My main fields of interest are Theoretical Computer Science, Algebraic Graph Theory, Coding Theory, Expander graphs, and Graphs of High Girth. Before that I was a postdoc at the University of Toronto. I receive my Ph.D. in 2002 from the Hebrew University.