<div dir="ltr">Hi folks, just a reminder of Friday's great program (below). We have a snowstorm to look forward to tonight thru Thursday night, but we're not going to let that stop us.<div><br></div><div><a href="http://www.google.org/publicalerts/alert?aid=fb443ba989074fec&hl=en&gl=US&source=web">http://www.google.org/publicalerts/alert?aid=fb443ba989074fec&hl=en&gl=US&source=web</a><br>
</div><div><br></div><div>Best, </div><div>Andy</div><div><br></div><div><div class="gmail_extra"><br><div class="gmail_quote">On Thu, Feb 6, 2014 at 11:54 AM, Andrew Drucker <span dir="ltr"><<a href="mailto:adrucker@mit.edu" target="_blank">adrucker@mit.edu</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div dir="ltr">The February CCI meeting will be held Friday, Feb. 14. We have a circuit complexity theme. See you there!<div>
<br></div><div>The talks start earlier this time (10:30) and are held in Princeton CS 105 (small auditorium). There is no PI meeting.<div>
<div><br></div><div><br></div><div>Schedule:</div><div><br></div><div>10:30 - 11:30am: Igor C. Oliveira, <span style="font-size:13px;font-family:arial,sans-serif"><b>Algorithms vs. Circuit Lower Bounds</b></span></div>
<div><br></div><div>11:30 - 12:30pm: Anup Rao, <b style="font-family:arial,sans-serif">Circuits with Large Fan-In</b></div><div><br></div><div>12:30 - 2:00pm: Lunch break</div><div><br></div><div>2:00 - 4:00pm (with short break): Benjamin Rossman, <b><span style="font-family:arial,sans-serif;font-size:13px">Formulas vs. Circuits for Small Distance Connectivity</span></b></div>
<div><br></div><div><br></div><div><br></div><div>Abstracts:</div><div><br></div><div><br>
</div><div><span style="font-family:arial,sans-serif;font-size:13px"><b>Algorithms vs. Circuit Lower Bounds</b></span><br style="font-family:arial,sans-serif;font-size:13px">Igor Oliveira (Columbia U.)<br><br style="font-family:arial,sans-serif;font-size:13px">
<span style="font-family:arial,sans-serif;font-size:13px">We survey the techniques behind different theorems of the form "algorithm for a circuit class C implies non-uniform lower bounds against C", touching upon areas such as learning, compression, derandomization, and satisfiability algorithms. We also discuss a tight relation (w.r.t. circuit depth) between the existence of nontrivial proofs for tautologies in a class C and lower bounds against C, observe some connections involving a few meta-results of this flavor, and point out directions for further research.</span><br style="font-family:arial,sans-serif;font-size:13px">
<span style="font-family:arial,sans-serif;font-size:13px"> </span><br style="font-family:arial,sans-serif;font-size:13px"><span style="font-family:arial,sans-serif;font-size:13px">The presentation will be mainly based on the survey report [ECCC TR13-117], and includes joint work with A. Klivans and P. Kothari [KKO13].</span><br>
</div><div><br></div><div><span style="font-family:arial,sans-serif;font-size:13px">------------------------------</span><span style="font-family:arial,sans-serif;font-size:13px">------------------------------</span><span style="font-family:arial,sans-serif;font-size:13px">------------------------------</span><span style="font-family:arial,sans-serif;font-size:13px">------------------------------</span><span style="font-family:arial,sans-serif;font-size:13px">------------------------------</span><span style="font-family:arial,sans-serif;font-size:13px">------------------------------</span><span style="font-family:arial,sans-serif;font-size:13px">---</span><span style="font-family:arial,sans-serif;font-size:13px"><br>
</span></div><div><span style="font-family:arial,sans-serif;font-size:13px"><br></span></div><div><div><font face="arial, sans-serif"><b>Circuits with Large Fan-In</b></font></div><div>Anup Rao (U. Washington)</div><div>
<p>
<font face="arial, helvetica, sans-serif">We consider boolean circuits where every gate in the circuit may compute an arbitrary function of k other gates, for a parameter k. We give an explicit function f : {0, 1}<span style="vertical-align:4pt">n </span>→ {0, 1} that requires at least Ω(log<span style="vertical-align:4pt">2 </span>n) non-input gates in this model when k = 2n/3. When the circuit is restricted to being depth 2, we prove a stronger lower bound of n<span style="vertical-align:4pt">Ω(1)</span>, and when it is restricted to being a formula, our lower bound is strengthened to Ω(n<span style="vertical-align:4pt">2 </span>/k logn) gates.</font></p>
<p><font face="arial, helvetica, sans-serif">Our model is connected to some well known approaches to proving lower bounds in complexity theory. Optimal lower bounds for the Number-On-Forehead model in communication complexity, or for bounded depth circuits in AC<span style="vertical-align:-1pt">0</span>, or for bounded depth monotone circuits, or extractors for varieties over small fields would imply strong lower bounds in our model. On the other hand, new lower bounds for our model would prove new time-space tradeoffs for branching programs and impossibility results for (fan-in 2) circuits with linear size and logarithmic depth. In particular, our lower bound gives a different proof for the best known time-space tradeoff for oblivious branching programs.</font></p>
<p><font face="arial, helvetica, sans-serif">Joint work with Pavel Hrubes.</font></p></div></div><div><span style="font-family:arial,sans-serif;font-size:13px"><br></span></div><div><span style="font-size:13px;font-family:arial,sans-serif">------------------------------</span><span style="font-size:13px;font-family:arial,sans-serif">------------------------------</span><span style="font-size:13px;font-family:arial,sans-serif">------------------------------</span><span style="font-size:13px;font-family:arial,sans-serif">------------------------------</span><span style="font-size:13px;font-family:arial,sans-serif">------------------------------</span><span style="font-size:13px;font-family:arial,sans-serif">------------------------------</span><span style="font-size:13px;font-family:arial,sans-serif">---</span><span style="font-family:arial,sans-serif;font-size:13px"><br>
</span></div><div><span style="font-family:arial,sans-serif;font-size:13px"><br></span></div><div><b><span style="font-family:arial,sans-serif;font-size:13px">Formulas vs. Circuits for Small Distance Connectivity</span><br style="font-family:arial,sans-serif;font-size:13px">
</b>Benjamin Rossman (National Institute of Informatics, Tokyo)<br><br style="font-family:arial,sans-serif;font-size:13px"><span style="font-family:arial,sans-serif;font-size:13px">In this talk, I will present recent results which give the first super-polynomial separation in the power of bounded-depth (unbounded fan-in) boolean formulas vs. circuits. Consider the elementary fact that every depth-d circuit of size S is equivalent to a depth-d formula of size at most S^d. We show that a blow-up of S^Ω(d) is necessary in the worst case for all d <= logloglog S. (Previously no lower bound better than S^Ω(1) was known for any super-constant d.) This result follows from a novel formula-size lower bound for the problem of Distance-k st-Connectivity. As a further corollary, we obtain a tight Ω(log k) lower bound on the depth of polynomial-size circuits solving Distance-k st-Connectivity for all k <= loglog n. (This improves the previous Ω(loglog k) lower bound of Beame, Impagliazzo, Pitassi (1998) and matches the O(log k) upper bound from Savitch's algorithm.)</span></div>
<div><span style="font-family:arial,sans-serif;font-size:13px"><br></span></div></div></div></div>
</blockquote></div><br></div></div></div>