Theory-Meet Talk Series

Spring 2008

The Friday Theory-Meet talks are a forum for computer science theory grad students to share their work and interests with each other. Talks include presentations of students' own work, papers we like, or cover topics that we want to jointly learn. The atmosphere is very informal and the underlying assumption is that everyone needs to understand each talk completely. That is, we rather have a talk with less contents but that we can follow than a talk full of results, none of which is well explained.

Subscribe Contact Ashwin Lall.
Location Computer Studies Building 703 (in the lower right)
Date/time Fridays, 4:00 pm
The talks are typically scheduled ad hoc. If you want to present something, just let know Piotr or Ashwin.
This talk series was started in the Spring semester of 2005 and has been running uninterrupted since then.

Spring 2008 Schedule
Date Speaker Topic Links
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
Date Speaker Topic Links
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
Date Speaker Topic Links
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!
Abstract: TBA
-
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
Date Speaker Topic Links
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
Date Speaker Topic Links
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
Date Speaker Topic Links
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
Date Speaker Topic Links
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
Date Speaker Topic Links
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

This page is based on html by Matt Post. Currently maintained by Piotr Faliszewski.