The Second Western New York Theory Day

Friday, November 2, 2007

Introduction

The Western New York Theory Day series is a joint project of the theory groups at Rochester Institute of Technology, the University at Buffalo, and the University of Rochester. The meetings are twice-yearly and rotate between the three schools. The two "visiting" schools usually provide the speakers.

These meetings bring people together in a friendly, informal atmosphere to hear about recent research advances in theoretical computer science. The meetings are open to the public, and all are warmly invited to attend.

Program

Location

The Theory Day will be held at:

Directions to UB (North Campus)

Please send email to Diane VanNatter (dmv3@cse.buffalo.edu) to request a parking permit. This will permit you to park in faculty/staff parking (Furnas Lot) and without charge in the Visitor's Lot (Fronczak Lot). The parking permit needs to be mailed to you, so please request this well in advance.

Organizers

Abstracts

Guarantees for the Success Frequency of an Algorithm for Finding Dodgson-Election Winners
Chris Homan, Rochester Institute of Technology

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

On the Complexity of Elementary Modal Logics
Henning Schnoor, Rochester Institute of Technology

 
Modal logic is used widely in various areas of computer science, for
example artificial intelligence and cryptography. The complexity of the
satisfiability problem for various modal logics has been investigated
since the 1970s, usually with proving results for each logic on a
case-by-case basis. We prove a very general classification for a wide
class of relevant logics: Many important subclasses of modal logics can
be obtained by restricting the allowed models with first-order Horn
formulas. We show that the satisfiability problem for each of these
logics is either in NP or PSPACE-hard, and prove matching PSPACE upper
bounds for many of them.

Adaptive Annealing: A Near-optimal Connection between Sampling and Counting
Daniel Stefankovic, University of Rochester

We present a near-optimal reduction from approximately counting the
cardinality of a discrete set to approximately sampling elements of
the set. Our result is set in the framework of approximating the
partition function $Z$ of a discrete system, such as the Ising model,
the matchings, or colorings of a graph. The typical approach to
estimating the partition function $Z(\beta)$ at some desired (inverse)
temperature $\beta^*$ is to define a sequence, which we call a {\em
cooling schedule}, $\beta_0=0<\beta_1<\dots<\beta_\ell=\beta^*$ where
$Z(0)$ is trivial to compute and the ratios $Z
(\beta_{i+1})/Z(\beta_i)$ are easy to estimate by sampling from the
distribution corresponding to $Z(\beta_i)$. Previous approaches
required a cooling schedule of length $O^*(\ln{A})$ where $A=Z(0)$,
thereby ensuring that each ratio $Z(\beta_{i+1})/Z(\beta_i)$ is
bounded. We present a cooling schedule of length $O^*(\sqrt{\ln{A}})$.
For well-studied problems such as estimating the partition function of
the Ising model, or approximating the number of $k$-colorings or
matchings of a graph, our cooling schedule is of length $O^*(
\sqrt{n})$, which yields an overall savings of $O^*( n)$ in the
running time of the approximate counting algorithm compared to
previous results.

Joint work with Santosh Vempala and Eric Vigoda.

The space-complexity of estimating the entropy of a stream
Ashwin Lall, University of Rochester

We can define the entropy of a stream over items {1, \ldots, n}
to be the sum: H = -\sum_i (m_i/m)\log{m_i/m}, where m_i is the frequency
of the i'th item and m is the total number of items in the stream (by
convention, 0\log{0} = 0). In this talk we will discuss the space usage of
a one-pass, streaming algorithm for computing H.

We will present an (\epsilon, \delta)-approximation algorithm for H that
is based on the seminal work of Alon, Matias, and Szegedy. We give bounds
on how much space the algorithm requires, based upon some reasonable
assumptions. We will then generalize this problem to the case where we
wish to compute the entropy between pairs of nodes in a network and show
how to use Indyk's stable distribution sketch data structure to solve this
problem.

This talk is based on joint works with Mitsu Ogihara, Jim Xu, Vyas Sekar,
Hui Zhang, Chuck Zhao, Oliver Spatscheck, and Jia Wang.