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

[Andrew Drucker]

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/20140206/1106c6e8/attachment-0001.html>
-------------- next part --------------
_______________________________________________
pvsnp-all mailing list
pvsnp-all at lists.cs.princeton.edu
https://lists.cs.princeton.edu/mailman/listinfo/pvsnp-all