## THEORY CANAL: The Rochester Theory Seminar Series 2006-2007 |

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 RIT and UR classes are in session) on the first and third (and sometimes, when a fifth exists, fifth) Monday of each month. (Due to slot demand, school holidays, and religious holidays, there are sometimes exceptions to that rule: Mondays of that form that we skip and Mondays not of that form that we don't skip. So see the schedule below for the actual dates.) 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.

**Chronological list of 12:30PM THEORY CANAL talks for the
2006-2007 academic year:**

**September 4, 2006, 12:30pm (No Meeting: Labor Day)****September 18, 2006, 12:30pm***Speaker*:**Joerg Rothe, Duesseldorf**

*Topic*:**An Improved Exact Algorithm for the Domatic Number Problem**The 3-domatic number problem asks whether a given graph can be partitioned into three dominating sets. We prove that this problem can be solved by a deterministic algorithm in time 2.695^n (up to polynomial factors) and in polynomial space. This result improves the previous bound of 2.8805^n, which is due to Bjorklund and Husfeldt (FOCS 2006). To prove our result, we combine an algorithm by Fomin et al. with Yamamoto's algorithm for the satisfiability problem (both presented at ISAAC 2005). In addition, we provide a randomized algorithm for the 3-domatic number problem that works well for graphs with bounded maximum degree and employs Schoening's approach to constraint satisfaction problems.

Joint work with T. Riege, H. Spakowski, and M. Yamamoto

**October 2, 2006, 12:30pm***Speaker*:**Lane Hemaspaandra, UR**

*Topic*:**The Consequences of Eliminating NP Solutions**Given a function based on the computation of an NP machine, can one in general eliminate some solutions? That is, can one in general decrease the ambiguity? This simple question remains, even after extensive study by many researchers over many years, mostly unanswered. However, complexity-theoretic consequences and enabling conditions are known. In this tutorial-style talk (and accompanying article) we look at some of those, focusing on the most natural framings: reducing the number of solutions of NP functions, refining the solutions of NP functions, and subtracting from or otherwise shrinking #P functions. We will see how small advice strings are important here, but we also will see how increasing advice size to achieve robustness is central to the proof of a key ambiguity-reduction result for NP functions

This talk corresponds to an expository paper joint with Piotr Faliszewski.

**October 16, 2006, 12:30pm**(No Meeting: UR Fall Break)**October 30, 2006, 12:30pm***Speaker*:**Bin Wei, UR**

*Topic*:**Active Learning**In some of machine learning applications, it is easy to attain a large corpus of untagged data, while asking for their tags is expensive, e.g, it is easy to attain the sound signal of people's talk, but it is not that easy to get what exactly the persons are talking about. Active learning is a technology that tries to minimize efforts in tagging data, that is, the number of tagged examples, while the performance of learning algorithm is kept at a certain level. This talk will be about my some of my reading in this area.

**November 6, 2006, 12:30pm***Speaker*:**Nayantara Bhatnagar, Georgia Tech**

*Topic*:**The Effect of Boundary Conditions on the Mixing Rates of Markov Chains**Many natural Markov chains undergo a phase transition as a temperature parameter is varied; a chain can be rapidly mixing (polynomial time) at high temperature and slowly mixing (exponential time) at low temperature. Even at low temperature, it is believed that the boundary conditions of a spin system (a type of model motivated by statistical physics) can determine whether a local Markov chain mixes quickly or slowly, but this has only been proved for models defined on trees.

We demonstrate that the mixing time of Broder's Markov chain for sampling perfect and near-perfect matchings does have such a dependence on the environment when the underlying graph is the square-octagon lattice. We show the same effect occurs for a related chain on the space of Ising and ``near-Ising'' configurations on the two-dimensional Cartesian lattice.

This is joint work with Sam Greenberg and Dana Randall

**November 20, 2006, 12:30pm***Speaker*:**Ashwin Lall, UR**

*Topic*:**Lower Bounds Through Communication Complexity**In the communication complexity model two parties (typically called Alice and Bob), who have non-overlapping but jointly complete parts of the input, wish to compute some function of the input. The communication complexity of the function at input size $n$ is then the largest number of bits that the parties have to communicate using the {\em best} protocol to compute the function. There are no bounds on the computational power of either party and the only resource being measured is the number of bits communicated.

Communication complexity has proved to be a very useful tool for getting lower bounds for an assortment of problems. In this talk I will introduce the area and survey some selected examples of using communication complexity techniques to produce lower bounds in other areas.

**December 4, 2006, 12:30pm***Speaker*:**Ivona Bezakova, RIT**

*Topic*:**Analysis of Sequential Importance Sampling for Contingency Tables**

The sequential importance sampling (SIS) algorithm has gained considerable popularity for its empirical success. One of its noted applications is to the binary contingency tables problem, an important problem in statistics, where the goal is to estimate the number of $0/1$ matrices with prescribed row and column sums. We give a family of examples in which the SIS procedure, if run for any subexponential number of trials, will underestimate the number of tables by an exponential factor. This result holds for any of the usual design choices in the SIS algorithm, namely the ordering of the columns and rows. These are apparently the first theoretical results on the efficiency of the SIS algorithm for binary contingency tables. Finally, we present experimental evidence that the SIS algorithm is efficient for row and column sums that are regular. Our work is a first step in determining the class of inputs for which SIS is effective.

This is joint work with Alistair Sinclair, Daniel Stefankovic, and Eric Vigoda.

**January 29, 2007, 12:30pm***Speaker*:**Ming Zhong, UR**

*Topic*:**Popularity-Driven Performance Optimization for Distributed Data-Intensive Systems**Many distributed data-intensive applications exhibit highly skewed data access popularities. We study the problem of exploiting such skewness to improve the performance of various applications, including web search engines, distributed file/storage systems, cooperative proxy caches, and unstructured p2p networks. We model the problem as classical convex optimization problems and approximate their optimal solutions. We also validate our approximate solutions on data access traces collected from real-life running systems.

**February 5, 2007, 12:30pm***Speaker*:**Mitsunori Ogihara, UR**

*Topic*:**A Complexity-Related Talk****February 19, 2007, 12:30pm***Speaker*:**Piotr Faliszewski, UR**

*Topic*:**On the Autoreductions of Functions**I will present some recent results on autoreducibility of complete functions. A function is autoreducible if there is a polynomial-time algorithm that computes the function on each input x given access to an oracle that outputs the value of the function on a requested input y, provided that y is different from x. In particular, I will show that #P parsimonious-complete functions have autoreductions of a very simple form. I will also present the relations between autoreducibility, closure properties of function classes, and algebraic properties of complete functions. This is joint work with Mitsunori Ogihara.

**March 5, 2007, 12:30pm (No Meeting: RIT's Spring Break)****March 19, 2007, 12:30pm***Speaker*:**Stanislaw Radziszowski, RIT**

*Topic*:**Demise of MD5 and SHA-1/Designing the New Hash**A hash function H:{0,1}* -> {0,1}

^{m}produces an m-bit digest of an arbitrary message, file, or even an entire file system. Typically, one wants hash functions to be easy to compute, but also infeasible to invert or to find collisions (pairs of inputs which hash to the same value). Hash functions are fundamental cryptographic primitives, and they are used extensively in authentication, preserving data integrity, digital signatures, and many other security applications. The two most widely used hash functions are MD5 (Message Digest, m=128) and SHA-1 (Secure Hash Algorithm, m=160), the latter supported by the US government as a standard FIPS-180-2. The collisions for MD5 were found three years ago, and by now they can be produced quickly by software available on the Net. The SHA-1 algorithm seems also to be in trouble (and other algorithms in the SHA family, with m=256, 384, 512, might follow). No collisions for SHA-1 have been found so far, but attacks much better than the simple birthday attack approach have been designed. Breaking SHA-1 soon is a likely possibility.On January 23, 2007, NIST (National Institute of Standards and Technology) announced an initiative to design a new hash for this century, to be called AHS (Advanced Hash Standard). The competition will be open and it is planned to conclude in 2012. These developments are quite similar to the recent history of symmetric block ciphers - breaking of the DES (Data Encryption Standard) and an emergence of the AES (Advanced Encryption Standard) in 2001 as the winner of a multiyear NIST competition.

This talk will outline the attacks on MD5 and SHA-1 and overview a likely scenario of what the teams submitting new designs for the AHS will consider.

**April 2, 2007, 12:30pm***Speaker*:**Christopher Homan, RIT**

*Topic*:**Guarantees for the Success Frequency of an Algorithm for Finding Dodgson-Election Winners**Dodgson's election system elegantly satisfies the Condorcet criterion. However, determining the winner of a Dodgson election is known to be $\Theta_2^p$-complete [HHR97] (see also [BTT89]), which implies that unless P=NP no polynomial-time solution to this problem exists, and unless the polynomial hierarchy collapses to NP the problem is not even in NP. Nonetheless, we show that when the number of voters is much greater than the number of candidates (although the number of voters may still be polynomial in the number of candidates), a simple greedy algorithm very frequently finds the Dodgson winners in such a way that it "knows" that it has found them, and furthermore the algorithm never incorrectly declares a nonwinner to be a winner.

**April 16, 2007, 12:30pm***Speaker*:**Ilka Schnoor, University of Hannover**

*Topic*:**Algebraic tools for Constraint Satisfaction**In the constraint satisfaction context the Galois correspondence between clones and co-clones involving polymorphisms has received a lot of attention. However, it fails if we are interested in a reduction giving equivalence instead of only satisfiability-equivalence. By refining both structures (the clones and the co-clones) into strongly partial clones and weak systems one obtains a Galois correspondence that fulfills all requirements we need for equivalence preserving reductions.

We develop a technique that allows to apply this correspondence for complexity-related questions. As an example of the usefulness of our construction, we show how to obtain very short proofs of complexity classifications in this context.

**Special Announcement: *Friday* April 20, 2007 (First Western New York Theory Day)**Please refer to http://www.cs.rit.edu/~eh/theoryday.html for the detailed information.

**April 30, 2007, 12:30pm***Speaker*:**Eric Brelsford, RIT**

*Topic*:**M.S. Thesis-Work-in-Progress Presentation: Approximating Some Election Problems**We initiate the definition of optimization problems in these systems and attempt to characterize their approximability. We show that some of the problems are not approximable assuming P \neq NP. These results include specific answers for a few control problems and more general solutions in the case of bribery.

The seminar series is open to public, and is being organized this year by Lane Hemaspaandra and Ming Zhong (with Bin Wei as elf-in-training in the spring) 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).