[CSDM] [pvsnp-all] Reminder: CCI meeting schedule - Friday, Feb. 14

[Andrew Drucker]

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.

http://www.google.org/publicalerts/alert?aid=fb443ba989074fec&hl=en&gl=US&source=web

Best,
Andy


On Thu, Feb 6, 2014 at 11:54 AM, Andrew Drucker <adrucker at mit.edu> wrote:

> The February CCI meeting will be held Friday, Feb. 14.  We have a circuit
> complexity theme.  See you there!
>
> The talks start earlier this time (10:30) and are held in Princeton CS 105
> (small auditorium).  There is no PI meeting.
>
>
> Schedule:
>
> 10:30 - 11:30am:  Igor C. Oliveira,  *Algorithms vs. Circuit Lower Bounds*
>
> 11:30 - 12:30pm:  Anup Rao,  *Circuits with Large Fan-In*
>
> 12:30 - 2:00pm:  Lunch break
>
> 2:00 - 4:00pm (with short break): Benjamin Rossman,  *Formulas vs.
> Circuits for Small Distance Connectivity*
>
>
>
> Abstracts:
>
>
> *Algorithms vs. Circuit Lower Bounds*
> Igor Oliveira (Columbia U.)
>
> 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.
>
> The presentation will be mainly based on the survey report [ECCC
> TR13-117], and includes joint work with A. Klivans and P. Kothari [KKO13].
>
> ------------------------------------------------------------
> ------------------------------------------------------------
> ---------------------------------------------------------------
>
> *Circuits with Large Fan-In*
> Anup Rao (U. Washington)
>
> 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}n → {0, 1} that requires at least Ω(log2 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Ω(1), and when it
> is restricted to being a formula, our lower bound is strengthened to Ω(n2 /k logn)
> gates.
>
> 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 AC0, 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.
>
> Joint work with Pavel Hrubes.
>
> ------------------------------------------------------------
> ------------------------------------------------------------
> ---------------------------------------------------------------
>
>
> *Formulas vs. Circuits for Small Distance Connectivity *Benjamin Rossman
> (National Institute of Informatics, Tokyo)
>
> 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.)
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://imap.math.ias.edu/pipermail/csdm/attachments/20140212/0f2738c0/attachment.html>
-------------- next part --------------
_______________________________________________
pvsnp-all mailing list
pvsnp-all at lists.cs.princeton.edu
https://lists.cs.princeton.edu/mailman/listinfo/pvsnp-all