ELC Mini-Workshop on Boolean Function Complexity (C01)

Date: Feb. 24th (Tue)
Time: 15:00 - 17:00

This is an informal seminar for discussing various aspects of
the complexity of Boolean functions, which we hope to be a
good starting point of our new collaboration on this topic.
For starting our disucssion, we will have the following two
talks.

Title : Strong ETH holds for Resolution with Bounded Read
Speaker: Navid Talebanfard (ELC C01 PD)

Abstract: Strong Exponential Time Hypothesis (SETH) states that
k-SAT requires time complexity 2^{(1 - c_k)n} for some c_k -> 0
as k -> infinity. Of course this is stronger that NP != P and
hence verifying this hypothesis remains way beyond our reach at
the moment. However we can ask whether currently known algorithms
or classes of algorithms are consistent with SETH. We construct
unsatisfiable k-CNF formulas which require resolution refutations
of size at least 2^{(1 - c_k)n} where each variable in the proof
is resolved at most a bounded number of times. Prior
to this work such a lower bound was known only for tree-like and
regular resolution.

This is a joint work with Ilario Bonacina.

Title: On restricting no-Junta Boolean function and
       It's application on the degree lower bound
Speaker: MingChuan Yang (National Taiwan ChaoTong Univ.)

Abstract: Let f be a Boolean function depending on n variables. We
prove that at least one of its subfunction derived from a restriction
depends on the remaining n-1 variables, for some variable. This
existent result suggests a possible way to deal with general Boolean
functions via its subfunctions. We can apply this idea to obtain a
degree lower bound of representing polynomials over finite rings.

(Host: Osamu Watanabe watanabe@is.titech.ac.jp)
(Please let me know if anyone wants to join it via polycom.)