"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, University of Illinois at Urbana-Champaign

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 (Enterprise) JavaBeans, Microsoft's COM/DCOM and OMG's CORBA component models are the major component technologies. Almost all of these have been specified in a natural language. Specifying components in a natural language is ambiguous to the software systems developers. The use of formal techniques helps to express components and consequently component-based software systems precisely. We show an example of theoretical foundation for JavaBeans component technology that leads towards a theoretical foundation of software components. The formal model presented supports system division into a number of interconnected components. We adopt the notion of refinement to formalize the replaceability of software components.

"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.

"An Online Scheduling Algorithm for Non-Preemptive, Equal-Length Jobs Using Two Identical Machines"
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.