| [Schedule]
11/6 (Thu) Room #501 A-B (5F)
14:00-15:00 Kenya Ueno (B02, Kyoto U.), Exact Algorithms for 0-1 Integer Programs with Linear Equality Constraints
15:30-17:00 open problems & free discussion
11/7 (Fri) Room #501 A-B (5F)
10:00-11:00 Jun Tarui (A03, U. Electro-Communications), Depth-First Search using O(n) bits
11:15-12:15 Suguru Tamaki (A02, Kyoto U.), On the complexity of randomness extractors
14:00-15:00 Kazuhisa Makino (A01, Kyoto U.), Posimodular function optimization
15:30-17:00 open problems & free discussion
11/8 (Sat) International Conference Room (1F)
10:00-11:00 Ramamohan Paturi (invited, UC San Diego), Fine-grained Complexity and Satisfiability
11:15-11:55 Kazuyuki Amano (B02, Gunma U.), Graph Partition and Communication Complexity
14:00-15:00 Osamu Watanabe (PI, Tokyo Institute of Technology), A Short Implicant of a CNF Formula with Many Satisfying Assignments
15:30-17:00 open problems & free discussion
18:00- dinner
11/9 (Sun) International Conference Room (1F)
10:00-11:00 Stefan Schneider (invited, UC San Diego), A Satisfiability Algorithm for Depth Two Threshold Circuits and 0-1 Integer Linear Programming
11:15-11:45 Kei Uchizawa (C03, Yamagata U.), Lower Bounds for Linear Decision Trees with Bounded Weights
14:00-15:00 Oliver Kullmann (invited, Swansea U.), Good SAT translations: approaches via resolution and monotone circuit bounds
15:30-17:00 open problems & free discussion
11/10 (Mon) Room #501 A-B (5F)
10:00-12:00 open problems & free discussion
[Talk Slides and Abstracts]
- Kenya Ueno, Exact Algorithms for 0-1 Integer Programs with Linear Equality Constraints
http://www.lab2.kuis.kyoto-u.ac.jp/~tamak/elc/booleanfunctions2014/ueno.pdf
In this talk, we will present O(1.415^n)-time and O(1.190^n)-space
exact algorithms for 0-1 integer programs where constraints are linear
equalities and coefficients are arbitrary real numbers. Our manuscript
on these results (arXiv:1405.6851) will be renewed before the
workshop. We will also discuss ongoing work on computational
experiments by using random 0-1 integer programs.
- Jun Tarui, Depth-First Search using O(n) bits
http://www.lab2.kuis.kyoto-u.ac.jp/~tamak/elc/booleanfunctions2014/tarui.pdf
- Suguru Tamaki, On the complexity of randomness extractors
http://www.lab2.kuis.kyoto-u.ac.jp/~tamak/elc/booleanfunctions2014/tamaki.pdf
Randomness extractors for structured sources such as bit-fixing and
affine sources are useful in proving circuit lower bounds. One reason
is that they inherit the property of being extractors after
restriction. In this talk I will survey known results on the
complexity of such extractors, especially focusing on lower bounds
obtained by restriction method. Also, I will present some open
questions related to this topic.
- Ramamohan Paturi, Fine-grained Complexity and Satisfiability
http://www.lab2.kuis.kyoto-u.ac.jp/~tamak/elc/booleanfunctions2014/paturi.pdf
- Stefan Schneider, A Satisfiability Algorithm for Depth Two Threshold Circuits and 0-1 Integer Linear Programming
http://www.lab2.kuis.kyoto-u.ac.jp/~tamak/elc/booleanfunctions2014/schneider.pdf
- Kei Uchizawa, Lower Bounds for Linear Decision Trees with Bounded Weights
http://www.lab2.kuis.kyoto-u.ac.jp/~tamak/elc/booleanfunctions2014/uchizawa.pdf
We consider a linear decision tree $T$ such that the sum of the
absolute values of the integer weights of a linear threshold function
at each internal node is at most $w$, and prove that if $T$ has size
(i.e., the number of leave) $s$, rank $r$, and computes a Boolean
function $f$, then there exists a depth-2 threshold circuit that
computes $f$ and has $s(2w+1)^{r}$ threshold gates with weight at most
$(2w+1)^{r+1}$ in the bottom level. Combining a known lower bound on
size of depth-2 threshold circuits, we can obtain a $2^{\Omega (n/\logw)}$
lower bound on the size of linear decision trees computing
Inner-Product function modulo 2, which improves on the previous bound
$2^{\sqrt{n}}$ if $w=2^{o(\sqrt{n})}$.
- Oliver Kullmann, Good SAT translations: approaches via resolution and monotone circuit bounds
I wish to give an overview on our work regarding aspects of a theory of
good SAT translations ("encodings"). The main tools are various "hardness
measures" for conjunctive normal forms, based on certain stable forms of
resolution complexity, extended to satisfiable CNFs via a worst-case
approach. The basic dimensions are:
1. tree-resolution versus full-resolution
2. absolute versus relative hardness (taking auxiliary variables into
account or not).
Relative hardness is closely related to monotone circuit complexity,
while the stronger approach, absolute hardness, needs new tools.
In my talk I will discuss the basic definitions, and give an overview
on our results.
[Organizers]
Kazuhisa Makino (A01, Kyoto U.)
Kazuhisa Seto (A02, Seikei U.)
Suguru Tamaki (A02, Kyoto U.)
|