|
Spring 2008 Schedule
|
3/21/2008
|
Ashwin Lall |
Max2SAT via SDP.
|
Abstract:
I will present an approximation algorithm for the Max2SAT problem using the semidefinite programming approach. Based on Chapter 26 of [Vaz01].
|
|
[Vaz01]
|
3/14/2008
|
Piotr Faliszewski |
Introduction to Semidefinite Programming
|
Abstract:
I will present the basics of semidefinite programming, its relationship to
strict quadratic programming, vector programming, and an application to the
max-cut problem. Based on Chapter 26 of [Vaz01].
|
|
[Vaz01]
|
3/14/2008
|
Satyaki Mahalanabis |
Density Estimation in Linear Time with Preprocessing
|
Abstract: We consider the problem of choosing a
density estimate from a set of distributions ${\cal F}$,
minimizing the $L_1$-distance to an unknown
distribution. Devroye and Lugosi analyze two algorithms
for the problem: Scheff\'e tournament winner and minimum
distance estimate. The Scheff\'e tournament estimate
requires fewer computations than the minimum distance
estimate, but has strictly weaker guarantees than the
latter. We focus on the computational aspect of density
estimation. We present two algorithms, both with the same
guarantee as the minimum distance estimate. The first one,
a modification of the minimum distance estimate, uses the
same number (quadratic in $|{\cal F}|$) of computations as
the Scheff\'e tournament. The second one, called
``efficient minimum loss-weight estimate'', uses only a
linear number of computations, assuming that ${\cal F}$ is
preprocessed. We also give examples showing that the
guarantees of the algorithms cannot be improved and
explore randomized algorithms for density estimation.
This is joint work with Daniel Stefankovic.
|
|
---
|
2/29/2008
|
Theory Students |
Theory Research at UofR
|
Abstract: Theory grad students from UofR present some highlights of their research.
|
|
--
|
2/22/2008
|
Ilka Schnoor |
Perfect Philogeny Haplotyping
|
Abstract: Talk continued.
|
|
[Elb07]
|
2/15/2008
|
Ilka Schnoor |
Perfect Philogeny Haplotyping
|
Abstract:
Haplotypes describe genetic information. It is a goal to catalog and
relate all human haplotypes. Although it is possible to extract
haplotypes from human cells, it is very expensive. However, it is
comparatively easy to obtain genotype information which is less detailed.
Haplotyping refers to algorithmic methods to retrieve the underlying
haplotypes from given genotypes. I introduce combinatorial problems that
model haplotyping questions and give complexity results presented in a
diploma thesis from Mchael Elberfeld.
|
|
[Elb07]
|
2/8/2008
|
Ashwin Lall |
Probabilistic Games
Abstract: I will present and motivate
probabilisitic streams, a variant of standard streaming in
which a distribution over streams is presented as a stream
itself. The goal is to compute the expected value of some
aggregation function over the stream distribution. I will
focus specifically on the problem of computing the
expected AVERAGE of such a stream. This talk is based on
[JKV07].
|
|
[JKV07]
|
2/1/2008
|
Piotr Faliszewski |
Weighted Voting Games and Power Indices
|
Abstract: I will present a simple theoretical model
of weighed voting, the weighted voting games, together with two very
natural notions of the power of the voters, namely, Banzhaf and
Shapley-Shubik power indices. I will show that computing both Baznhaf
and Shapley-Shubik is #P-complete (for some notions of
#P-completeness) and then I will show that comparing values of the
power index of a player in two games is PP-complete.
|
|
[FH08]
|
|
Fall 2007 Schedule
|
11/16/2007
|
Qi Ge/All |
Approximation Algorithms Series, Meeting 6
|
Abstract:
Problem solving session! Yay!
|
|
[Vaz01]
|
11/9/2007
|
Ashwin Lall |
Approximation Algorithms Series, Meeting 5
|
Abstract:
We talked about approximation solutions for Max-SAT.
|
|
[Vaz01]
|
11/2/2007
|
--- |
2nd WNY Theory Day (Buffalo)
|
Abstract:
The talk is cancelled; we all went to Buffalo and listened to some good theory work.
Oh, and Ashwin gave a cool talk on streaming algorithms!
|
|
2nd WNY Theory Day
|
10/19/2007
|
Satyaki Mahalanabis |
Approximation Algorithms Series, Meeting 4
|
Abstract:
Today we come back to the Set Cover problem, but perform the analysis via
linear programming methods. (Chapter 12.)
|
|
[Vaz01]
|
10/19/2007
|
Piotr Faliszewski |
Approximation Algorithms Series, Meeting 3
|
Abstract:
Today we cover FPTAS for the Bin Packing problem. (Chapter 9.)
|
|
[Vaz01]
|
10/12/2007
|
Piotr Faliszewski |
Approximation Algorithms Series, Meeting 2
|
Abstract:
Today we cover FPTAS for the Knapsack problem. (Chapter 8.)
|
|
[Vaz01]
|
10/5/2007
|
Qi Ge |
Approximation Algorithms Series, Meeting 1
|
Abstract:
Today we start the Approximation Algorithm Series; a semminar
based on the book ``Approximation Algorithm'' by V. Vazierani,
embedded into the theory-meet structure. Today we cover chapters
1 and 2 (Introduction and Set Cover problem).
|
|
[Vaz01]
|
9/28/2007
|
Satyaki Mahalanabis |
Uniform Deviation Inequalities
|
Abstract:
"Uniform Deviation Inequalities", chapter 3 of "Combinatorial Methods in Density Estimation" by Luc Devroye and Gabor Lugosi.
|
|
[DL01]
|
9/21/2007
|
Qi Ge |
Counting Perfect Matchings in Planar Graphs (Cont'd)
|
--
|
9/14/2007
|
Qi Ge |
Counting Perfect Matchings in Planar Graphs
|
Abstract:
My topic is the Pfaffian and Counting the number of perfect matchings in
planar graphs. I will give the definition of Pfaffian, its relation to
determinant and how to count the number of perfect matchings in planar
graphs in polynomial time. The stuff is about 40 years' old but has
recently been used as basis in the fascinating Holographic algorithms.
|
|
--
|
|
Spring 2007 Schedule
|
4/20/2007
|
--- |
WNY Theory Day (no talk in grad student semminar)
Abstract: There is no talk; students will attend
WNY Theory Day at RIT.
|
|
--
|
4/6/2007
|
Ashwin Lall |
The Magic of Expansion
|
Abstract: Continuation of the last week's talk.
|
|
--
|
3/30/2007
|
Ashwin Lall |
The Magic of Expansion
Abstract: In this talk I will define and show the
existence of so-called magical (expander) graphs. I will
then show how such graphs can be applied to create
error-correcting codes and for derandomization of
algorithms. This presentation is based on the first
lecture in a series on expanders by Linial and
Wigderson.
|
|
--
|
3/23/2007
|
Piotr Faliszewski |
Towards an Exponential Analog of the Karp-Lipton Theorem
|
Abstract: I will talk about some of my work on
exponential-time reductions and their application to
obtaining an equivalent of a Karp-Lipton theorem for
NEXP. Early version of this work is presented in [Fal04].
|
|
[Fal04]
|
3/2/2007
|
Theory Students |
Presentation of the Theory Research at URCS
|
Abstract: Three students, Chengliang, Ming, and Ashwin
presented their research and described their interests in theoretical
computer science.
|
|
--
|
2/23/2007
|
Piotr Faliszewski |
Bribery in Copeland Elections
|
Abstract: Copeland is a tournament-based voting
system. Each voter v_i specifies a preference list, a
strict total order among candidates >_{v_i}, and for every
two candidates p and c we compute how many voters prefer p
to c and how many prefer c to p. The candidate that wins
such a head-to-head contest gets one Copeland point. (In
the case of a tie nobody gets a point.) In the end, the
candidates that get most Copeland points are declared
winners.
I will show that the bribery problem for this system is
NP-complete. I will also show a polynomial-time algorithm
for the case where voters are irrational (that is, their
preference lists are not strict total orders but have more
flexibility).
|
|
[FHHR07]
|
2/16/2007
|
Ashwin Lall |
Stable distributions and their application to streaming algorithms
|
Abstract:
I will speak about stable distributions and their application to streaming algorithms. The main goal of my talk will be to present an algorithm of Indyk
(FOCS 2000) to compute L_p distances of streams.
|
|
[Ind00]
|
2/9/2007
|
Qi Ge |
An interesting talk about theory!
|
-
|
2/2/2007
|
Satyaki Mahalanabis |
Maximizing the probability of reaching a target vertex from a source vertex
|
Abstract: Consider a graph, with each edge of which
is associated a probability distribution on R (set of
reals). The following paper tries to solve the problem
of maximizing the probability of reaching a target
vertex from a source vertex in this graph, given a a
time limit in which to do so. The presentation will
focus on the algorithm given in this paper for normal
(gaussian) edge distributions.
Presentation is based on paper [NKBM06].
|
|
[NKBM06]
|
|
Fall 2006 Schedule
|
12/1/2006
|
Ashwin Lall |
Playing in MUD: Massive Unordered Distributed data
|
Abstract:
I will be talking tomorrow
on the complexity of processing Massive, Unordered, Distributed data (affectionately abbreviated MUD).
It's a new model for streaming algorithms where streaming computation
can be distributed (and computed symmetrically in parallel). My talk will
be based on the paper [FMSSS06] that I will not expect you to have read.
|
|
[FMSSS06]
|
11/17/2006
|
Piotr Faliszewski |
Self- and Autoreducibilities within Function Classes
|
Abstract: In this talk I will talk about the notions of self- and
autoreducibility for function classes, particulalry concentrating on
#P. This talk presents some ongoing research with Mitsu Ogihara.
|
|
&ndash
|
11/10/2006
|
Ashwin Lall |
Inapproximability results for MAX3SAT
|
Abstract:
I'm going to take a step back from what we've been doing so far and focus
on how we jump from the PCP theorem to inapproximability results. In particular,
I'm going to step through the argument why we cannot approximate MAX3SAT to any
arbitrary ratio (using the PCP theorem). I'll be closely following the first
14 pages of chapter 19 in this web draft by Arora and Barak
|
|
[AB]
|
10/27/2006
|
Piotr Faliszewski |
Introduction to the applications of PCP (cont'd further) |
[Kho05]
|
10/20/2006
|
Piotr Faliszewski |
Introduction to the applications of PCP (cont'd) |
[Kho05]
|
10/13/2006
|
Piotr Faliszewski |
Introduction to the applications of PCP
|
Abstract:
This talk starts a series of workshop-like presentations of the applications
of the PCP theorem. In these talks we will go over the recent survey paper
by Subhash Khot [Kho05].
|
|
[Kho05]
|
9/29/2006
|
Qi Ge |
Approximation algorithms for finding optimal disjoint paths on DAGs
|
&ndash
|
9/29/2006
|
Ashwin Lall |
Counting the number of distinct items
|
Abstract:
Counting the number of distinct items in a stream is a fairly fundamental
operation and there exist some neat algorithms for solving the problem.
I'll also discuss some lower bounds that have been found. Along the way I'll
reintroduce the area of streaming and provide some background and motivation
for the topic.
|
|
&ndash
|
9/29/2006
|
Piotr Faliszewski |
Some issues with #P functions
|
Abstract:
I will present a paper by Pagourtzis and Zachos [PG06] on the complexity
of counting functions with easy decision version. Let f be a #P function.
f's decision version is the problem of deciding whether f(x) > 0 for a given x.
Pagourtzis and Zachos show that the class of #P functions that have
easy decision versions and are self-reducible is exactly the closure
of TotP under parsimonious reductions. TotP is the class of functions
that count the number of computation paths of NP machines.
|
|
&ndash
|
|
Summer and Spring 2006 Schedule
|
5/19/2006
|
Piotr Faliszewski |
New Analysis of the Find-Union Algorithm
Abstract:
Union-Find problem is that we have some disjoint sets, and we can
perform two operations:
(a) test if two elements are in the same set, and
(b) union two sets (as specified by giving two elements in them).
Such operations are useful e.g., if we have a graph, but vertices
and edges arrive to us on-line, but we want to be able to each time
be able to say if two given vertices are in the same connected components.
This problem is, e.g., described in CLRS with a not-so-beautiful potential
function based analysis. The paper I had to read describes a very clear
top-down approach.
|
|
&ndash
|
---
|
--- |
Throught the Spring 2006 the seminar held discussions and tutorials regarding Daniel
Stefankovic's class on Markov Chains.
|
---
|
|
Fall 2005 Schedule
|
12/2/2005
|
Remco Loos |
Thoery of Splicing Systems (Part 2).
|
&ndash
|
11/25/2005
|
Remco Loos |
Thoery of Splicing Systems (Part 1).
|
&ndash
|
11/18/2005
|
Piotr Faliszewski |
Introduction to Computational Social Choice Theory.
|
Abstract:
I will attempt to sort of mention a kind of area of study, namely
the complexity of modifying results of elections, given different manipulation
capabilities. Thus the problem is: Given voting scheme and everyone's preferences,
is there a way to modify something so that our favourite candidate wins, or
so that our least liked candidate loses.
|
|
&ndash
|
11/11/2005
|
Ashwin Lall |
Kolmogorov Complexity Tutorial.
|
&ndash
|
10/27/2005
|
Ivona Bezakova |
The Markov Chain Technique (Part 2).
|
&ndash
|
10/14/2005
|
Ivona Bezakova |
The Markov Chain Technique (Part 1).
|
Abstract:
I will give an introductory talk about Markov Chains. My running
example will be the Broder chain which I introduced on Monday (don't
panick, I'll go through it again). Thus, we will describe a fully
polynomial approximation scheme for counting the number of perfect
matchings in dense graphs [result of Jerrum and Sinclair, basis for most
follow up work].
|
|
&ndash
|
10/7/2005
|
Piotr Faliszewski |
Very Sparse Languages.
|
Abstract:
I will make an attempt at presenting a recent result of Falk Unger,
namely that:
(1) SAT many-one bit-reduces to a sparse set, and
(2) SAT does not many-one bit-reduce to a poly-log sparse set unless
polynomial hierarchy collapses.
These results are analogs of Mahaney's result that there are no NP-hard
sparse sets unless P=NP, but in the leaf-language setting.
|
|
&ndash
|
9/30/2005
|
Bin Wei |
Introduction to the Goals and Concepts of Data Mining.
|
&ndash
|
9/23/2005
|
Remco Loos |
Computing with DNA.
|
&ndash
|
9/16/2005
|
Piotr Faliszewski |
Autoreductions of Complete Sets.
|
Abstract:
The talk will be about autoreducibility of NP-complete sets. I will
start from the beginning, so I will define what autoreducibility is,
and what are its two main flavors (many-one, and Turing), and I
will show that:
- All NP-complete sets are Turing autoreducible (Beigel, Feigenbaum)
- All NP-complete sets are many-one autoreducible (Glasser et al.)
I will also muse on a certain problem regarding many-one autoreductions
that I was thinking about recently.
|
|
&ndash
|
|
Summer 2005 Schedule
|
8/12/2005
|
Ashwin Lall |
Ramsey Numbers.
|
Abstract:
Ramsey Numbers, Difference Ramsey Numbers and using the Probabilistic
Method to get lower bounds on them.
I will assume no background knowledge and promise that more than one
color will be used in the talk!
|
|
&ndash
|
8/5/2005
|
Piotr Faliszewski |
What Is Known About P vs NP.
|
Abstract:
I will give a talk about fun stuff regarding P vs NP
question. In particular, I will touch-base on the topic of P vs NP being formally
independent in certain proof systems.
|
|
&ndash
|
7/29/2005
|
Bill Sherer |
Introduction to Non-Blocking Synchronization.
Abstract:
I will start with a discussion of progress in non-blocking
synchronization, covering wait-freedom, lock-freedom, and
obstruction-freedom, then expand into linearizability theory, which is a
technique that has been introduced to prove correctness of concurrent data
structures. I will then cover elimination theory and linearizability of
partial methods, and will wrap up with a presentation of an
elimination-based non-blocking exchange channel to tie everything
together.
I'll aim for the whole talk to take about an hour, but the content can be
adjusted on the fly if we want to focus in on some of it more than the
|
|
&ndash
|
7/22/2005
|
Matt Post |
The Inside-Outside Algorithm.
|
Abstract:
I'll be walking through
the inside-outside algorithm, an efficient way to set
probabilities on a probabilistic context-free grammar
in a way that maximizes the likelihood of a training
corpus.
|
|
&ndash
|
6/10/2005
|
Rahul Tripathi |
"Oracles are subtle but not malicious" by Scott Aaronson
|
[Aar05]
|
6/3/2005
|
Ashwin Lall |
Alon-Matias-Szegedy algorithm for estimating frequency moments.
|
&ndash
|
|
Spring 2005 Schedule
|
4/15/2005
|
Rahul Tripathi |
Job search/options for Theory People
|
[Aar05]
|
4/1/2005
|
Ashwin Lall |
Bloom Filters.
|
&ndash
|
?/?/2005
|
Piotr Faliszewski |
Three sets in NP between P and NP-com.
|
Abstract:
The topic of the talk was how to create three sets
A, B, C in P, such that under plausible complexity-theoretic
assumptions one would have that none of them is in P, none
of them is NP-complete, and A < B < C (that is, A reduces to B,
B reduces to C, but C does not reduce to B, and B does not
reduce to A).
|
|
&ndash
|
?/?/2005
|
Rahul Tripathi
| On a certain combinatorial problem with relation to complexity theory.
|
&ndash
|
3/11/2005
|
Piotr Faliszewski
| Leaf-languages as a way of defining complexity classes.
|
&ndash
|
3/4/2005
|
Ashwin Lall |
Introduction to communication complexity.
|
&ndash
|
2/25/2005
|
Rahul Tripathi |
On the Power of Unambiguity in Alternating Machines.
Abstract:
Unambiguity is a well-familiar concept in the context of
nondeterministic polynomial-time computation: A language L is in UP
(unambiguous polynomial-time) if and only if there is an NPTM N such
that for all input x, x in L => N(x) has exactly one accepting path
and x not in L => N(x) has zero accepting path.
The concept of unambiguity can be generalized to alternating
polynomial-time computation. An alternating computation captures
computation of stacks of NP machines, where language of one NP machine
serves as an oracle to the preceding stacks of NP machines. Unlike the
case of Nondeterministic polynomial-time machines, this generalization
leads to three different hierarchies of unambiguous computation in
alternating polynomial-time machines.
I will mention our results on relativized limits of unambiguous
computation in alternating polynomial-time machines. In tomorrow's
talk, I will present a proof of the following generalization of
Hartmanis-Hemachandra's result about robustly categorical computation
in NP machines:
For any k, if an oracle alternating polynomial-time Turing machine N
preserves k-level of alternation in the presence of every oracle, then
for any oracle A, the langauge accepted by N^{A} is computable in
P^{\Sigma^{p}_{k} \oplus A}. Here \Sigma^{p}_{k} is the kth level of
the polynomial hierarchy and \oplus is the set join operation: L_1
\oplus L_2 = \{0w | w \in L_1\} \cup \{1w | w \in L_2\}. Thus,
robustly bounded-level unambiguous polynomial-time alternating
machines require only weak database (oracle) access in the presence of
any database.
The talk will conclude with a bunch of interesting open questions. A
preliminary TR can be found at TR-851 (see link).
|
|
TR-851
|
2/18/2005
|
Chengliang Zhang |
Hardness of finding reference affinity groups.
|
Abstract:
I will talk about the basic concept and properties of reference
affinity.
|
|
[ZOSD04]
|
2/11/2005
|
Piotr Faliszewski |
Ladner's Theorem, or What's Inside NP.
|
&ndash
|
2/4/2005
|
Rahul Tripathi |
On Approximation Algorithms for Finding Shortest Paths.
|
&ndash
|
|
|
|