Abstracts
"Time-Space Lower Bounds for the
Polynomial-Time Hierarchy on Randomized Machines"
Speaker: Scott Diehl, University of Wisconsin-Madison
In this talk, we establish lower bounds for the running time of randomized machines with two-sided error
which use a small amount of workspace
to solve complete problems in the polynomial-time hierarchy. In particular, we show that for integers k
> 1, a randomized machine with
two-sided error using subpolynomial space requires time 
to solve QSATk, where QSATk denotes the problem of
deciding the validity of
a Boolean first-order formula with at most k-1 quantifier alternations. This represents the first time-space lower
bounds for complete problems in
the polynomial-time hierarchy on randomized machines with two-sided error.
Corresponding to k = 1, we show that a randomized machine with one-sided error using subpolynomial
space requires time 
to decide the set of Boolean tautologies. As a corollary,
this gives the same lower bound
for satisfiability on deterministic machines,
improving on the previously best known
such result.
Joint work with Dieter van Melkebeek
"Reducing Tile Complexity for Self-Assembly Through Temperature Programming"
Speaker: Robert T. Schweller, Northwestern University
We consider the tile self-assembly model and how tile complexity can be
eliminated by permitting the temperature of the self-assembly system to be
adjusted throughout the assembly process. To do this, we propose novel
techniques for designing tile sets that permit an arbitrary length m
binary number to be encoded into a sequence of O (m) temperature changes
such that the tile set uniquely assembles a supertile that precisely encodes
the corresponding binary number. As an application, we show how this provides a
general tile set of size O(1) that is capable of uniquely assembling
essentially any 
square, where the assembled square is
determined by a temperature sequence of length O (log n) that encodes a
binary description of n. This yields an important decrease in tile
complexity from the required 
for almost all n when the temperature
of the system is fixed. We further show that for almost all n, no
tile system can simultaneously achieve both 
temperature complexity and 
tile complexity, showing that both versions
of an optimal square building scheme have been discovered. This work suggests
that temperature change can constitute a natural, dynamic method for providing
input to self-assembly systems that is potentially superior to the current
technique of designing large tile sets with specific inputs hardwired into the
tileset.
"Power-aware
Scheduling for Makespan and Flow"
Speaker: David Bunde,
We present ongoing work on power-aware scheduling. In this setting, jobs must
be scheduled on a processor that can run at different speeds and consumes more
power the faster it runs. We give a linear-time offline algorithm to minimize
the makespan on a single processor using a bounded amount of energy. We also
give offline algorithms for minimizing the makespan and total flow of equiwork
jobs on multiple processors with a shared power supply having a bounded amount
of energy.
"Removing Even Crossings"
Speaker: Michael Pelsmajer, Illinois Institute of Technology - Chicago
An edge in a drawing of a graph is called even if it intersects every other
edge of the graph an even number of times. Pach and Toth proved that a graph
can always be redrawn such that its even edges are not involved in any
intersections. We give a new, and significantly simpler, proof of a slightly
stronger statement. We show two applications of this strengthened result: an
easy proof of a theorem of Hanani and Tutte (not using Kuratowski's theorem),
and the result that the odd crossing number of a graph equals the crossing
number of the graph for values of at most 3 . We begin with a disarmingly
simple proof of a weak (but standard) version of the theorem by Hanani and
Tutte.
Joint work with Marcus
Schaefer and Daniel Stefankovic.
"On the High Information Content of a Class of Objects with Low Algorithmic Complexity"
Speaker: Adrian German, Indiana University
We describe a simple rewriting system with three colors which, starting from a
single black cell (trit) produces strings of increased Chaitin randomness
(patternless-ness) through iterated rewriting. In particular we show that in
the limit the strings produced are normal (in the Borel sense) that is, every
pattern of length p appears with a frequency of
in
k-th step of the iterated rewriting, where 
is the length of the string, and k (the index
number of the rewriting process) goes to infinity. Note that in the case of
finite strings for the frequency to mean anything n must be significantly
larger than the number of patterns under consideration 
.
It is also shown that each of the strings produced through rewriting have low
algorithmic (Chaitin, Kolmogorov) complexity, which leads to an apparent
contradiction. Thus we argue that the scope of the definition of descriptional
complexity is too wide and thus too weak to distinguish between complexities
that do not lead to incompleteness results, and is thus responsible for the
apparent conflict. We propose a variant of the definition that takes into
account the specific choice in representation, and consequently is able to make
the distinction between the individual levels of complexity induced by such a
choice.
"Edge-list-colorability
of planar graphs with no two adjacent triangles"
Speaker: Dan Cranston, University of Illinois at Urbana-Champaign
We show that if G is a planar graph with no two triangular faces sharing an
edge and 
, then G is (
-edge-list-colorable. We use the technique of discharging.
"Dynamic
well-separated pair decomposition made easy"
Speaker: John Fischer, University of Illinois at Urbana-Champaign
Well-separated pair decomposition (WSPD) is a means of concisely encapsulating
approximate distances among members of a finite point set P. We
focus on WSPD defined using as an underlying data structure a skip
quadtree defined over P. By randomly shifting the quadtree in
advance, we show that upon point insertion or deletion, the
WSPD can be updated in time logarithmic in |P| with high
probability.
"Finding Points on Characteristic 2 Elliptic Curves with Applications to Message
Embedding"
Speaker: Andrew Shallue, University of Wisconsin-Madison
While fast probabilistic algorithms for finding points on elliptic curves over finite fields are well-known, the
problem of derandomizing these algorithms is not so well studied. For elliptic
curves over finite fields of characteristic two, we give an algorithm for
finding a nontrivial point in deterministic polynomial time. We also extend the
algorithm to the encoding problem, so that now messages can be encoded as
points on such curves in deterministic polynomial time for use in elliptic
curve cryptography, in particular the ECC analogs of Massey-Omura and ElGamal.
"Towards a Theoretical Foundation for Software Components"
Speaker: Bhim Prasad Upadhyaya, Maharishi Univ. of Management, Iowa
Component based software development focuses on building software systems by assembling existing software
components. This makes the systems
more maintainable, reduces development time and minimizes development as well as maintenance costs.
Sun's (
"Flexible Word
Design and Graph Labelling"
Speaker: Manan Sanghi, Northwestern University
Motivated by emerging applications for DNA code word design, we consider
the problem of labeling the vertices of a given input graph with equal length
binary strings of minimal length such that the Hamming distance is small
between words of adjacent nodes and large between words of
non-adjacent nodes. For general graphs we provide algorithms that bound the
word length with respect to either the maximum degree of any
vertex or the number of edges in either the input graph or its
complement. We further provide multiple types of recursive, deterministic algorithms for trees and
forests, and provide an improvement for forests that makes use of
randomization. We also consider
generalizations of this problem to weighted graphs and graphs with optional
edges. Finally, we explore the extension from simple adjacency queries
to more general distance queries and show how to obtain distance
labelings for rings and paths by applying properties of hypercube
traversal.
Speaker: Mark Pedigo, Saint Louis University
We present an online algorithm which schedules non-preemptive, equal
length jobs using two identical machines. Our goal is to maximize the
number of jobs which can be scheduled by their deadlines. Each job has an
arbitrary release date and deadline, which is revealed to the scheduler
only upon its release time. We analyze this algorithm by comparing its
results to an optimal offline schedule. In this way, we show that the
algorithm is 3/2 competitive.
"A linear time algorithm for finding a p-center of a tree"
Speaker: James Pierce, Illinois Institute of Technology
The general facilities location problem is an optimization problem which
involves finding a set of central facilities which "best" serves the customers.
"Best" can be described in various ways depending on our notion of distance as
well as other constraints. We present a fast algorithm for solving a version of
this general facilities location problem.