## THEORY CANAL: The Rochester Theory Seminar Series |

The THEORY CANAL meeting (the Rochester Theory Seminar) is a joint project of the UR and RIT theory groups, and the focus is all areas of theoretical computer science. THEORY CANAL meets (when classes are in session) on the first, third, and---when there is a fifth Monday---fifth Monday of each month. (Due to slot demand, school holidays, and religious holidays, there are frequent exceptions to that rule: Mondays of that form that we skip and Mondays not of that form that we don't skip.) The talks start at 12:30PM and typically take 60 to 90 minutes.

The meetings are held in Room 703, Computer Studies Building, University of Rochester, Rochester, NY 14627.

The meetings are open to the public; all are very welcome.

**But first, FYI, some 11AM regular department seminar talk dates
for 2004-2005 that might be of particular interest:**

- Sept. 13, 2004, Joerg Rothe, Duesseldorf.
- Oct. 11, 2004, Ronitt Rubinfeld, MIT.
- Dec. 5, 2004, Eva Tardos, Cornell.
- April 18, 2005, Sanjeev Arora, Princeton.

**September 13, 2004, 12:30pm***Speaker*:**Joerg Rothe, Duesseldorf**

*Topic*:**The Complexity of Young Elections, Exact-Four-Colorability, and Exact Domatic Number Problems**In this talk, three types of problems are classified according to their computational complexity. The following results are shown: 1. The winner problem for Young elections is complete for parallel access to NP. 2. Exact colorability problems are complete for the levels of the boolean hierarchy over NP. In particular, the problem Exact-Four-Colorability is complete for DP, the second level of this hierarchy. This solves an open question by Wagner. This result is based on a clever reduction by Guruswami and Khanna, which has the property that it never yields 4-colorable graphs. 3. Exact domatic number problems are complete for the levels of the boolean hierarchy over NP. All these results apply Wagner's technique of achieving completeness for various complexity classes.

**September 20, 2004, 12:30pm***Speaker*:**Lane Hemaspaandra, URCS**

*Topic*:**Advice for Semifeasible Sets and the Complexity-Theoretic Cost(lessness) of Algebraic Properties**This talk provides a tutorial overview of the advice complexity of the semifeasible sets---informally put, the class of sets having a polynomial-time algorithm that, given as input any two strings of which at least one belongs to the set, will choose one that does belong to the set. No previous familiarity with either the semifeasible sets or advice complexity will assumed, and when we include proofs we will try to make the material as accessible as possible via providing intuitive, informal presentations.

Karp and Lipton introduced advice complexity about a quarter of a century ago. Advice complexity asks, for a given power of interpreter, how many bits of ``help'' suffice to accept a given set. Thus, this is a notion that contains aspects both of informational complexity and of computational complexity. We will see that for some powers of interpreter the (worst-case) complexity of the semifeasible sets is known right down to the bit (and beyond), but that for the most central power of interpreter---deterministic polynomial time---the complexity is currently known only to be at least linear and at most quadratic.

While overviewing the advice complexity of the semifeasible sets, we will stress also the issue of whether the functions at the core of semifeasibility---so-called selector functions---can without cost be chosen to possess such algebraic properties as commutativity and associativity. We will see that this is relevant, in ways both potential and actual, to the study of the advice complexity of the semifeasible sets. We'll see also that the study of round-robin tournaments is deeply related to the advice complexity of the semifeasible sets.

**September 27, 2004, 12:30pm***Speaker*:**Harald Hempel, Jena**

*Topic*:**Inversion of Superlinear Verifiers is coNP-Hard**Everyone knows what inverting a function means. But what does inverting an NP problem or a verifier mean? How hard is it to invert an NP problem?

In this talk we will define and study inversions of NP problems (and their verifiers). We will show that inverting superlinear verifiers is always coNP-hard via applying an in-circuit-diagonalization technique, and we also will give a $\Sigma_2^p$ completeness result.

A related issue is the problem of recognizing whether a given machine actually computes a verifier. We will show that this is complete for the second level of the arithmetic hierarchy.

This is joint work with Edith Hemaspaandra of RIT and Lane Hemaspaandra of the University of Rochester.

**October 4, 2004, 12:30pm***Speaker*:**Ming Zhong, URCS**

*Topic*:**Non-uniform Random Sampling in Peer-to-Peer Networks via Biased Random Walks**Non-uniform random sampling is essential for many peer-to-peer network problems, such as randomized p2p topology construction, p2p routing, gossip-based broadcasting, network failure detection and load balancing etc. A natural way to achieve non-uniform random sampling is to use biased random walks. We are going to talk about how to configure biased random walks to satisfy the desired non-uniform sampling distribution. We will give analytical results on the mixing time of several biased random walks in common p2p network topolgies, such as Chord network, tori, random regular graphs and power-law graphs. We will also explain how our non-uniform random sampling algorithm can be applied to current p2p network problems.

**October 18, 2004, 12:30pm**(No Meeting: UR Fall Break)**November 1, 2004, 12:30pm***Speaker*:**Joel Seiferas, URCS**

*Topic*:**The AKS Sorting Network**The celebrated AKS sorting network of Ajtai, Komlos, and Szemeredi sorts n keys in parallel time O(log n). We'll try to understand and simplify its strategy and operation.

**November 8, 2004, 12:30pm***Speaker*:**Rahul Tripathi, URCS**

*Topic*:**The Simple Stochastic Game Problem**Simple stochastic games (SSGs) were introduced by Condon (1992) to study the power of logspace bounded randomized alternating machines. These games are variants of stochastic games (Shapley, 1953) in the game theory literature. A natural decision problem related to SSGs is the SSG value problem---given a two player simple stochastic game, decide whether the first player wins the game with probability at least 1/2 when both players use their best strategies. SSG value problem is among the rare combinatorial problems that belong to NP \intersect coNP (Condon 1992), but are not known to be in P. A polynomial-time algorithm for the simple stochastic game problem would imply that randomness does not increase the power of logspace bounded alternating machines.

In this talk, I will present some known results on the SSG value problem. If time permits, I will describe my work, related to this problem, with V. S. Anil Kumar while I visited the Los Alamos National Laboratory.

**November 15, 2004, 12:30pm***Speaker*:**Joan Lucas, SUNY-Brockport**

*Topic*:**Towards a Simpler Proof of the Four-Color Theorem: Connections to Rotations and Edge-Colorings in Binary Trees**

The famous Four-Color Problem of Planar Maps was first posed in 1852 and remained a tantalizing puzzle until Appel and Haken found a solution in 1977. But their solution was considered unsatisfactory to many because it lacked lucidity and required hours of electronic computation. More recently, in 1996, Robertson, Sanders, Seymour and Thomas published a new proof with improved computational aspects. However, there is not yet a proof that doesn't require the use of a computer.

In 1996, Czumaj and Gibbons showed that the Four-Color Problem is equivalent, by an optimally fast reduction, to a problem of optimally Edge-Coloring Pairs of same-sized Binary Trees (the CPBT problem). We present the recent work of Gibbons and Sant (2004) outlining several results and open problems concerning the CPBT problem, which could lead to a more elegant proof of the Four-Color Problem.

One approach is based on the well-known rotation operation of binary trees. We show how this operation can be combined with the process of constraining subsets of edges on the rotational path between two trees to be the same color. For several infinite-sized classes of tree pairs, a rotational path can provide solutions to the CPBT problem. Such a coloring can be found in linear time. Another approach concerns patterns of colorability within forms of regular-tree pairs. We describe the notions of parity, even-parity trees and odd-parity trees. In particular, there is a solution to CPBT for any pair of trees that have the same parity-sequence.

**November 29, 2004, 12:30pm***Speaker*:**Ashwin Lall, URCS**

*Topic*:**A Brief History of Streaming Algorithms**In this talk I will describe the streaming model of computation and give some motivations for studying it. I will then describe the problem of computing the frequency moments of items being sent over a stream and discuss some applications and results pertaining to this concrete problem.

**December 6, 2004, 12:30pm***Speaker*:**Rahul Tripathi, URCS**

*Topic*:**Understanding Relationships Between Quantum and Classical Complexity Classes: Separations, Collapses, and Closures**Over the past decade, quantum computing has emerged as a major contender to classical computing with far-reaching implications and challenges for the real world. Efficient quantum algorithms for problems such as the discrete logarithm and factoring have led researchers to rethink the foundations of classical cryptographic schemes.

Quantum complexity theory is the study of the computational power and the limitations of quantum computing. A major theme in quantum complexity theory is to understand the relationships between quantum and classical complexity classes. In this talk, I will illuminate this relationship by means of separations, collapses, and closure results involving quantum and classical counting classes.

The most central quantum complexity classes, EQP, BQP, and NQP (the quantum analogs of P, BPP, and NP), are known to be related to classical counting complexity classes. We prove that standard (relativizable) proof techniques cannot improve the best-known classical bounds for EQP and BQP significantly. For relationships between certain quantum and counting classes, we prove stronger results: No standard (relativizable) proof technique can show that every infinite set in one class has a nontrivial approximation in another class (even under the nondemanding approximation notion of merely having an infinite subset belonging to the other class). These results show the limitations of a broad class of proof techniques in resolving questions on relationship between quantum and classical complexity classes. We also obtain interesting consequences, in terms of the complexity of the polynomial hierarchy, of hypotheses involving the quantum complexity classes EQP, BQP, and NQP.

Though we will touch on this just briefly in the talk, our analysis leads to the resolution of important questions in classical complexity theory as well. The foremost among these is that, resolving a question open since the seminal 1994 counting class paper of Fenner, Fortnow, and Kurtz, we prove that the counting classes WPP and LWPP are not uniformly gap-definable.

This talk is based on joint work with Holger Spakowski and Mayur Thakur.

**January 17, 2005, 12:30pm**(No Meeting: Martin Luther King Day)**January 31, 2005, 12:30pm***Speaker*:**Chengliang Zhang, URCS**

*Topic*:**Reference Affinity: A Hierarchical Model of Data Locality**The big speed gap between the CPU and the memory system emerges almost at the same time the computer is invented and keeps increasing in the recent decades. No single technology can solve this problem by providing big and fast memory support that matches CPU. To address this problem, memory hierarchy is thus widely used in most current machines.

The effectiveness of the hierarchical memory system depends highly on the program locality. Thus, it is important to change the program to provide more locality. Yutao and the others developed a model of reference affinity which measures how closely a group of data are accessed together in a reference trace. It proves that the model gives a hierarchical partition of program data. At the top is the set of all data with the weakest affinity. At the bottom is each data element with the strongest affinity. Based on the theoretical model, they present k-distance analysis, a practical test for the hierarchical affinity of source-level data. The memory hierarchy can be used for array regrouping and structure splitting, which improve the program locality. Experiments show its effectiveness.

In this talk, I will show two theoretical results on the reference affinity model. The first is the complexity. We show that finding and checking affinity groups are in P when k=1 and k=2. When $k=3$, the checking problem is NP-complete, and the finding problem is NP-hard. The second is the uses. We show that reference affinity captures the hierarchical data locality from the trace of a hierarchical computation. As additional evidence, we cite empirical results for general-purpose programs.

**February 7, 2005, 12:30pm***Speaker*:**Stanislaw Radziszowski, RIT**

*Topic*:**How Small Can the Most Wanted Folkman Graph Be? Searching for a K**_{4}-free graph which is not a union of two triangle-free graphsWe discuss a branch of Ramsey theory concerning edge Folkman numbers and how computer algorithms could help to solve some problems therein. We write G -> (a1,...,ak;p) if for every edge k-coloring of an undirected simple graph G not containing K_p, a monochromatic K_ai is forced in color i for some 1 <= i <= k. The edge Folkman number is defined as Fe(a1,...,ak;p) = min{|V(G)| : G -> (a1,...,ak;p)}. Folkman showed in 1970 that this number exists for p > max(a1,...,ak).

In general, much less is known about edge Folkman numbers than the related and more studied vertex Folkman numbers, where we color vertices instead of edges. Fe(3,3;4) involves the smallest parameters for which the problem is open, namely the question, ``What is the smallest order N of a K4-free graph, for which any edge 2-coloring must contain at least one monochromatic triangle?'' This is equivalent to finding the order N of the smallest K4-free graph which is not a union of two triangle-free graphs. It is known that 16 <= N (an easy bound), and it is known through a probabilistic proof by Spencer (later updated by Hovey) that N <= 3*10^9. We suspect that N <= 127. This talk will discuss the difficulties in obtaining better bounds on N, and some computational evidence why it is very likely that even N < 100.

**February 21, 2005, 12:30pm***Speaker*:**Piotr Faliszewski, URCS**

*Topic*:**Separating the Notions of Length-Decreasing Self-Reducibility and Auto-Reducibility, Provided P\neq PSPACE.**Recently it was shown that all PSPACE-complete languages (as well as all complete languages for many many other classes, including NP) are autoreducible.However, it remains an oppen issue whether all PSPACE-complete (NP-complete) problems are Turing self-reducible.

We consider a simpler problem, namely whether all PSPACE-complete (NP-complete) problems are length-decreasing self-reducible. We show that if all PSPACE-complete languages are length-decreasing self-reducible then PSPACE = P and that the same implication holds for many other natural complexity classes (like NP, e.g., if all NP-complete sets are length-decreasing self-reducible then NP = P). We also show that our technique can be applied to L and NL to show that unless L = NL, not all NL-complete sets are log-space length-decreasing self-reducible.

Our results also give two nonconditional results: * Not all PSPACE-compelete sets are log-space length-decreasing self-reducible. * Not all EXP-complete sets are length-decreasing self-reducible.

**March 7, 2005, 12:30pm**(No Meeting: UR Spring Break)**March 14, 2005, 12:30pm***Speaker*:**Vladimir Kolesnikov, University of Toronto**

*Topic*:**Strong Conditional Oblivious Transfer and Computing on Intervals**We consider the problem of securely computing the Greater Than (GT) predicate (also widely known as the Yao's two millionaires problem) and its generalization -- securely determining membership in a union of intervals. We approach these problems from the point of view of Q-Conditional Oblivious Transfer (Q-COT). Q-COT is an oblivious transfer that occurs {\em iff} predicate Q evaluates to true on the parties' inputs. We are working in the semi-honest model with {\em computationally unbounded} receiver.

We propose: (i) a stronger, simple and intuitive definition of COT, which we call {\em strong} COT, or Q-SCOT. (ii) A simpler and more efficient one-round protocol for securely computing GT and GT-SCOT. (iii) A simple and efficient modular construction reducing SCOT based on membership in a union of intervals (UI-SCOT) to GT-SCOT, producing an efficient one-round UI-SCOT.

**March 28, 2005, 12:30pm***Speaker*:**Kadathur Lakshmanan, SUNY-Brockport**

*Topic*:**Two Graph Problems in Fault Diagnosis**In this talk, I will present two graph problems in the context of fault diagnosis. In both cases, we use graph models for systems consisting of several components. Our interest is to place sufficient number of alarms/detectors so that a fault at any single component can be detected and uniquely diagnosed. Both problems are intractable. The optimization problems are NP-hard, but approximating an optimal solution within a factor that is logarithmic in the number of nodes in the graph is possible.

In the first case, we consider systems that can be modeled as directed acyclic graphs such that nodes represent components of the system and directed edges represent fault propagation between components. The alarm minimization problem is NP-hard even when restricted to three level graphs in which all nodes have outdegree two or less. A polynomial approximation algorithm that guarantees that the ratio of the number of alarms placed to the optimum required is within a factor that is logarithmic in the number of nodes will be presented. Moreover, by showing a reduction from the minimum dominating set problem to the minimum alarm set problem, we argue that the performance guarantee is tight within a constant factor.

In the second case, we consider systems that can be modeled as undirected graphs such that nodes represent components of the system and undirected edges represent the fault detection capability of the detectors. Since the algorithmic issues are similar to the problem above, we focus only on the graph theoretic formulation in this talk. We also reformulate the problem as one of intruder detection in safeguarding a secure facility and present three versions of interest. We relate the cardinalities of the optimal solutions under those three versions.

**April 4, 2005, 12:30pm***Speaker*:**David Eisenstat, URCS**

*Topic*:**Computation in Networks of Passively Mobile Finite-State Sensors**Suppose we are monitoring the health of a flock of birds. We have equipped each bird with a small sensor that can detect whether it is ill. These sensors have a tiny (read: constant) amount of memory, radio receivers, and low-power transmitters that they can use to communicate with each other at close range. We have no control over when sensors can communicate, but we expect the interactions that take place to be reasonably random. After broadcasting a global start signal with a more powerful transmitter, we want the sensors to reach consensus on whether at least five birds are ill so that later, we can recapture any one of the birds and read off the correct result.

The above is an example of a model of computation introduced by Angluin, Aspnes, Diamadi, Fischer, and Peralta in their paper "Computation in Networks of Passively Mobile Finite-State Sensors" (PODC 2004). I will be presenting results from this paper and subsequent work, including efforts by Angluin and myself to characterize the power of this model and others similar to it.

**April 13, 2005, 11:00am***Speaker*:**Jeffrey Shallit, University of Waterloo**

*Topic*:**Avoidability in Words: New Results and Open Problems**Do there exist infinite words that do not contain squares, that is, subwords of the form xx, where x is a non-empty word? Axel Thue showed almost 100 years ago that the answer is "yes" over an alphabet of size 3, and thereby initiated the field of combinatorics on words. In this talk I will discuss several new avoidability results in words. This represents joint work with N. Rampersad, M.-w. Wang, J. Karhumaki, L. Ilie, and P. Ochem.

**April 18, 2005, 12:30pm***Speaker*:**You**

*Topic*:**"Problem show and tell" meeting**Reviving a semi-tradition, this meeting will be a "problem show and tell," which means you should (if you are a theory person) come in with an open problem to explain and discuss. We'll probably start with the graduate students. ;-}

The seminar series is open to public, and is being organized this year by Lane Hemaspaandra and Ming Zhong of UR and Edith Hemaspaandra of RIT. If you have any questions, please send email to ``lane'' or ``zhong'' (both in the domain cs.rochester.edu) or ``eh'' (in the domain cs.rit.edu).