Computational Complexity

Friday, April 02, 2004

 
More News from Dagstuhl

Posted by Lance

Another Guest Post from Dieter van Melkebeek

Thursday morning, Shuki Bruck gave the first talk at the workshop that dealt with actual Boolean circuits. He pointed out that cyclic circuits can be combinational and may allow us to realize Boolean functions with fewer gates and/or less delay. Consider the following circuit with inputs x1, x2, x3, and outputs f1, f2, f3, f4:

 |-----------------------------------|
 |                                   |
 |    x1       x2     -x1       x3   |
 |    |        |       |        |    |
 |    |        |       |        |    |
 |    v        v       v        v    |
 |                                   |
 |-> \/ ----> /\ ----> \/ ----> /\ --|

      |        |        |        |
      v        v        v        v

      f1       f2       f3       f4

Although the circuit is topologically cyclic, the outputs are well-defined and only depend on the inputs. (Look at the cases x1=0 and x1=1 separately.) A careful analysis shows that every acyclic circuit that outputs f1, f2, f3, and f4 needs at least 5 nonunary gates. Thus, circuits with feedback allow us to gain a factor of 4/5 in terms of number of gates needed to compute these functions. (As usual, we do not count negations.) Shuki presented a sequence of Boolean functions for which the reduction in the number of nonunary gates asymptotically reaches 1/2 if we only allow gates of fanin at most 2. He raised the question how significant the reduction can be if we allow larger fanin.

Thomas Thierauf presented an NC² algorithm for unique perfect matching. A perfect matching in a graph is a collection of disjoint edges that cover all vertices. It is known for some time how to decide the existence of a perfect matching and how to construct one in randomized NC²:

1. Assign random weights from a small range of integers to the edges of the graph such that with high probability there is at most one minimum weight perfect matching. If we are in the situation with a unique minimum weight matching M, we can decide whether a given edge belongs to M by evaluating two determinants of matrices with integer entries that are exponential in the weights. Since the weights are small, we can do the latter in NC².
2. Run the NC² algorithm on all edges in parallel and verify that the result is a perfect matching M.

It is open whether perfect matchings can be constructed deterministically in NC.

To decide whether a graph G has a unique perfect matching, Thomas first runs step 2 above (with unit weights). If that test fails, the algorithm rejects since G either has no perfect matching or has more than one. If the test is passed, the algorithm additionally verifies that G has no perfect matching M' other than M. Such an M' exists iff G contains a cycle that alternates between edges from M and edges in G-M. The latter can be cast as a reachability problem in a graph that is roughly a concatenation of directed copies of M and G-M. Since directed graph reachability can be computed in NC² and the input to the reachability problem can be computed in NC² by step 2 above, the additional test runs in NC², as does the entire algorithm.

On Friday, Oded Lachish discussed the current records on unrestricted circuit lower bounds for explicit functions in n Boolean variables. For circuits that can use any binary gate, the record dates back to 1984 and stands at 3n. For circuits that can use any binary gate except parity and its negation, the record has recently been improved from 4n - O(1) to 5n - o(n). Both records use the technique of gate elimination, and Oded conjectured that the 3n result can be improved along the lines of the recent 5n - o(n) result.

The workshop ended at noon on Friday. One statistic: among the 33 talks, 3 were blackboard only, 5 used handwritten slides, 1 printed slides, and 24 were computer presentations.

Finally, I have one suggestion for those readers who have attended a Dagstuhl seminar in the past. In a response to changes in financial support, the Dagstuhl office is requesting information about research publications that grew out of or have otherwise been significantly influenced by a Dagstuhl seminar. If you are an author of such a publication, please send the information to office@dagstuhl.de. Let's try to keep the wonderful tradition of Dagstuhl alive!

2:39 PM # 0 comments

Comment Feeds: This Post All