dtlee@EECS.NWU.EDU (Der-Tsai Lee) (11/10/90)
23rd MIDWEST THEORY CONSORTIUM**
McCORMICK SCHOOL OF ENGINEERING AND APPLIED SCIENCE
NORTHWESTERN UNIVERSITY
Saturday, December 1, 1990
11:00 - 11:25 Lance Fortnow (Univ. of Chicago)
Title: On the Random-Self-Reducibility of Complete Sets
11:25 - 11:50 Glenn Manacher (University of Illinois at Chicago)
Title: Efficient Algorithms for Interval Graphs and Circular-Arc Graphs
11:50 - 13:00 Lunch (Tech Room # 2730)
13:00 - 13:40 Rao Kosaraju (Johns Hopkins University)
Title: Circuit Value Problems and Their Applications
13:40 - 14:05 Greg N. Frederickson (Purdue University)
Title: Optimal Algorithms for Partitioning Trees
14:05 - 14:30 Jonathan Sorenson (University of Wisconsin-Madison)
Title: The $k$-ary GCD Algorithm
14:30 - 15:20 Coffee
15:20 - 16:00 Roberto Tamassia (Brown University)
Title: Dynamic Expression Trees and their Applications
16:00 - 16:25 Paul Purdom (Indiana University)
Title: Average Time for Satisfiability Problems with Clause Order Backtracking
16:25 - 16:50 Arthur Goldstein (University of Illinois at Urbana-Champaign)
Title: Unimodal Search and Kraft's Inequality
16:50 - 17:30 Informal Discussion
18:00 - Dinner (SEAPORT -- 6319 W. Dempster St., Morton Grove, IL)
For further information please contact:
D.T. Lee or M. Sarrafzadeh
Dept. of EE & CS
Northwestern Univ.
Evanston, IL 60208
dtlee@eecs.nwu.edu or majid@eecs.nwu.edu
708-491-5007 or 708-491-7378
We look forward to seeing you at the meeing.
ALL talks will be held in Lecture Room 4, Tech. Institute.
________________________________
**Supported by the National Science Foundation under Grant CCR-9017290.
*************************************************************************
ABSTRACTS
****************************************************************************
On the Random-Self-Reducibility of Complete Sets
Lance Fortnow
Department of Computer Science
University of Chicago
Informally, a function $f$ is {\it random-self-reducible} if the
evaluation of $f$ at any given instance $x$ can be reduced in
polynomial time to the evaluation of $f$ at one or more {\it random}
instances $y_i$. A set is random-self-reducible if its characteristic
function is. Random-self-reducibility plays a major role in many
areas of theoretical computer science, including average-case
complexity, lower bounds, interactive proof systems, zero-knowledge,
instance-hiding, pseudorandom number generation, and program checking.
In this paper, we generalize the previous formal definitions of
ran\-dom-self-re\-du\-ci\-bi\-li\-ty found in Abadi, Feigenbaum and
Kilian, and Feigenbaum, Kannan and Nisan. We show that, even under a
very general definition, sets that are complete for any level of the
polynomial hierarchy are not random-self-reducible, unless the
hierarchy collapses. In particular, NP-complete sets are not
random-self-reducible, unless the hierarchy collapses at the third level.
By contrast, we show that sets complete for the classes PP and ${\rm
MOD}_m{\rm P}$ are random-self-reducible.
(This research is joint work with Joan Feigenbaum.)
****************************************************************************
Efficient Algorithms for Interval Graphs and Circular-Arc Graphs
Glenn Manacher
Dept. of Math., Statistics and Computer Science
University of Illinois at Chicago
We will show that
a) The minimum-weight dominating set of an interval graphs, given the model,
can be found in time O(n log n);
b) The minimum-weight dominating set of a circular-arc graph, given the
model, can be found in time O(n**2 log log n);
c) If negative-weight vertices are permitted in minimum-weight dominating
set problems, the minimum-weight dominating set obviously includes all the
the negative-weight vertices. Nevertheless, oblivious, post-including, or
pre-elimination algorithms that one might suppose extend algorithms known to
work when the vertex weights are positive, in general fail when negative-
weight vertices are present. For instance, a) and b) above are known to work
with their stated complexity only for nonnegative vertex weights. Obvious
"extensions" all result in wrong algorithms.
d) Despite c), there IS a technique that assures constructively that any
serial or parallel algorithm working in some known time to find a minimum-
weight dominating set in a given class of graphs, given nonnegative weights,
can be transformed to an algorithm with the same complexity that will work
in the presense of negative weights.
****************************************************************************
Circuit Value Problems and Their Applications
Rao Kosaraju
Department of Computer Science
Johns Hopkins University
We first review the known techniques for tree evaluation and
their applications to other problems. We demonstrate that tree evaluation
can be viewed as a very simple generalization of parallel prefix computation.
We then explore the evaluation of more general cicuits. The talk includes
results on parallel algorithm design and the size of bounded width straight
line programs. We also pose several interesting open problems. A few of
these appear to be attractively simple.
The talk does not assume prior knowledge of results in this area.
****************************************************************************
Optimal Algorithms for Partitioning Trees
Greg N. Frederickson
Department of Computer Science
Purdue University
Parametric search is a powerful technique for solving a variety of
optimization problems, including graph problems. In parametric search,
a value must be chosen from a set of values, such that the value is the
largest (or the smallest) value in the set that passes a certain
feasibility test.
We study two parametric search problems on trees, whose previous best
algorithms had running times worse than the corresponding feasibility tests.
We present an approach that relies on the generation and searching of
partial orders, and the construction of sublinear feasibility tests.
Application of our techniques leads to linear-time (and hence optimal)
algorithms for two tree-partitioning problems.
****************************************************************************
The $k$-ary GCD Algorithm
Jonathan Sorenson
Computer Sciences Department
University of Wisconsin-Madison
In this talk we introduce the new $k$-ary greatest common divisor
(GCD) algorithm, a generalization of the binary algorithm.
Interestingly, this new algorithm has both a sequential version that
is very practical and parallel versions that rival the best
previous parallel GCD algorithms.
We show that for $k$ a prime power, the sequential $k$-ary GCD algorithm
has a $\Theta(n^2)$ worst-case running time on $n$-bit inputs.
However, in a multiple-precision implementation the $k$-ary
algorithm outperforms several other GCD algorithms, including the binary
algorithm by 40\%, and the Euclidean algorithm by a factor of 15.
Parallel versions of the algorithm include the following for the CRCW PRAM
model: an $O(n/\log n)$ time algorithm using $O(n^{1+\epsilon})$ processors,
and for $d\ge1$, an $O(\log^dn)$ time algorithm using
$\exp[ O( n / \log^dn) ]$ processors.
The first algorithm matches the complexity of the best previous
parallel GCD algorithm using a polynomial number of processors,
and the second algorithm is the first deterministic polylog time
GCD algorithm using a subexponential number of processors.
There also are EREW and CREW PRAM versions of the algorithm.
****************************************************************************
Dynamic Expression Trees and their Applications
Roberto Tamassia
Department of Computer Science
Brown University
We present a technique for dynamically maintaining a collection of arithmetic
expressions represented by binary trees (whose leaves are operands and whose
internal nodes are operators). A query operation asks for the value of an
expression (associated with the root of a tree). Update operations include
changing the value of an operand and combining or decomposing expressions by
linking or cutting the corresponding trees. Our dynamic data structure uses
linear space and supports queries and updates in logarithmic time. We also
present applications to layout compaction, constructive solid geometry, and the
dynamic maintenance of maximum flow and shortest path in series-parallel
digraphs.
(Joint work with R.F. Cohen.)
****************************************************************************
Average Time to Solve Satisfiability Problems with Clause Order Backtracking
Paul Purdom
Department of Computer Science
Indiana University
Clause order backtracking solves constraint satisfaction problems by
searching. If the problem haas a relation that is always false, then the
search stops. Otherwise the the first nontrivial relation (one that its not
always either true or false) is slected and the first variable that affect
the value of that relation is set each possible way. Subproblems are
generated by plugging in the value of the newly set variable and the search
is continued. This algorithm finds all solutions (in a compressed form) and
it is fast under a wide range of conditions. For the random clause model of
generating random satisfiability problems, this algorithm runs in polynomial
average time under a number of conditions, including those that result in the
average clause length being below 1 and those that result in the average
clause length increasing faster than the square root of the number of
variables (times a logarithmic factor).
****************************************************************************
Unimodal Search and Kraft's Inequality
Arthur Goldstein
Dept. of Computer Science
University of Illinois at Urbana-Champaign
A function is {\em unimodal} if it strictly increases to a unique maximum
and then strictly decreases. We study the problem of determining the
smallest possible interval containing the maximum of a unimodal function by
probing only at integer values. Our analyses are based on an unusual
Fibonacci version of Kraft's inequality.
****************************************************************************