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.
| 9:30 | -9:45 | Coffee and bagels |
| 9:45 | -10:45 | Liyu Zhang, University at Buffalo |
| The Informational Content of Canonical Disjoint NP-Pairs | ||
| 11:00 | -12:00 | Jonathan Buss, University of Waterloo |
| Hardness of Fixed-Parameter Problems: A Simple Approach | ||
| 12:00 | -1:45 | Lunch break |
| 1:45 | -2:45 | Piotr Faliszewski, University of Rochester |
| The Complexity of Bribery in Elections | ||
| 3:00 | -4:00 | Mitsunori Ogihara, University of Rochester |
| Time and Space Complexity for Splicing Systems |
The Theory Day will be held at
Room 70-3000 (the CS conference room; 3rd floor)
Golisano College of Computing and Information Sciences
Rochester Institute of Technology
102 Lomb Memorial Drive
Rochester, NY 14623-5608.
The Informational Content of Canonical Disjoint NP-Pairs
Liyu Zhang, University at Buffalo
We investigate the connection between propositional proof systems
and their canonical pairs. It is known that simulations between proof
systems translate to reductions between their canonical pairs.
We focus on the opposite direction and study the following questions.
Q1: Where does the implication can(f) \le_m can(g) => f\le_s g
hold, and where does it fail?
Q2: Where can we find proof systems of different strengths, but
equivalent canonical pairs?
Q3: What do (non-)equivalent canonical pairs tell about
the corresponding proof systems?
Q4: Is every NP-pair (A,B), where A is NP-complete, strongly
many-one equivalent to the canonical pair of some proof system?
In short, we show that Q1 and Q2 can be answered with `everywhere',
which generalizes previous results by Pudlak and Beyersdorff.
Regarding Q3, inequivalent canonical pairs tell that the proof systems
are not ``very similar'', while equivalent, P-inseparable canonical
pairs tell that they are not ``very different''.
We can relate Q4 to the open problem in structural complexity that
asks whether unions of disjoint NP-complete sets are NP-complete.
This demonstrates a new connection between proof systems,
disjoint NP-pairs, and unions of disjoint NP-complete sets.
This is joint work with Christian Glasser and Alan Selman.
Hardness of Fixed-Parameter Problems: A Simple Approach Jonathan Buss, Cheriton School of Computer Science, University of Waterloo
In the setting of fixed-parameter problems, hardness of a problem is generally measured in terms of the "weft" of a circuit. For example, the class W[1] comprises those problems reducible to weighted satisfiability for circuits having depth 2 and weft 1. This approach, however, requires considerable effort in order to prove the basic completeness results. I shall describe an alternative approach, with which one can define the W-hierarchy and prove completeness results without any mention of "weft" at all. The proofs follow closely the Cook/Karp proofs of the basic results of NP-completeness -- they use encodings of machine computations to give "generic" reductions. I shall outline how this approach has led to improvements in both upper bounds (e.g., SubsetSum) and lower bounds (e.g., for some problems regarding automata). This is joint work with T. Islam.
The Complexity of Bribery in Elections
Piotr Faliszewski, University of Rochester
Recently, social choice theory has received significant attention from the AI community. Researchers are solving planning problems via conducting elections between different alternatives, web search-engines use preference aggregation mechanism to combine rankings obtained through different criteria, and people envision societies of independent autonomous agents more and more vigorously. As a result, it is important to study the security of election systems and voting rules. One of the identified dangers for elections is bribery, i.e., the situation where an agent tries to affect the result of an election via convincing other agents to vote as he or she says. In this talk I will discuss the problem of bribery in elections from the computational perspective: I will show both election systems that are susceptible and resistant to bribery (i.e., election systems for which the problem of finding an optimal bribery is either in P or NP-hard) and I will present connections between bribery and strategic voting. This is joint work with Edith Hemaspaandra and Lane A. Hemaspaandra.
Time and Space Complexity for Splicing Systems
Mitsunori Ogihara, University of Rochester
The splicing system is a computational model in which words are produced by "word splicing"---a process that cuts any pair of words with certain patterns into two parts and then swaps the second part between the two. The splicing model, though known to be as powerful as the Turing machine model, has never been studied from a complexity theoretic viewpoint. In this talk I propose a notion of time complexity as well as a notion of space complexity, and then show some lower and upper bound results. In particular, I will show: (1) the languages produced by splicing systems having time complexity f(n) are accepted by f(n)-space-bounded one-way nondeterministic Turing machines, (2) the languages produced by splicing systems having time complexity f(n) include the languages accepted by pushdown automata with accepting computation paths in which stack height never exceeds f(n), and (3) the languages produced by splicing systems having polynomial space complexity are precisely those in NP. This is joint work with Remco Loos.