Hajim School Logo                                     URCS Mona Logo

Downward Collapses and Query Order

UR-CS Participating Faculty: Lane A. Hemaspaandra (= Lane A. Hemachandra)

Project Description

Query Order

Everyone knows that it makes more sense to first look up in your on-line datebook the date of the yearly Computational Complexity conference and then phone your travel agent to get tickets, as opposed to first phoning your travel agent (without knowing the date) and then consulting your on-line date book to find the date. In real life, order matters.

This project seeks to determine whether one's everyday-life intuition that order matters carries over to complexity theory. Does the order in which one accesses computational information sources matter? In particular, we study the importance of the order of queries when accessing two sets from the boolean hierarchy, and we also study the importance of the order of queries when accessing two sets from the polynomial hierarchy.

A particularly interesting domain for looking more generally at the issue of order of operations is the study of multimode attacks on elections. In our initial study of this, we mostly fixed the order in which the multiple prongs of multimode attacks occur. But what can one say about other orders, or about the extent to which order affects complexity, and affects the power of attacks?

Downward Collapses

The theory of NP-completeness does not resolve the issue of whether P and NP are equal. However, it does unify the issues of whether thousands of natural problems—the NP-complete problems—have deterministic polynomial-time algorithms. The study of downward collapse is similar in spirit. By proving downward collapses, we seek to tie together central open issues regarding the computing power of complexity classes. For example, one result obtained as part of this project shows that (for $k>2$) the issue of whether the $k$th level of the polynomial hierarchy is closed under complementation is identical to the issue of whether two queries to this level give more power than one query to this level. This project is additionally interested in cases where other unexpected features induce collapses, e.g., when results for sparse black boxes induce general-case results, or when results about multivalued functions induce collapses in the polynomial hierarchy.

References

1
This is a list of selected papers, from or related to this project, by University of Rochester authors. Links to essentially all Lane's conference and journal papers (and also his arXiv.org technical reports) can be found via the pointers from the related entries within Lane's entry at the DBLP project. Additionally, here is a link to Lane's complete publication list (note: that list does not itself have links to papers).
2
J.-Y. Cai, V. Chakaravarthy, L. Hemaspaandra, and M. Ogihara.
Competing provers yield improved Karp–Lipton collapse results.
Information and Computation, 198(1):1–23, 2005.
3
P. Faliszewski, E. Hemaspaandra, and L. Hemaspaandra.
Multimode control attacks on elections.
In Proceedings of the 21st International Joint Conference on Artificial Intelligence, pages 128–133. AAAI Press, July 2009.
4
P. Faliszewski, E. Hemaspaandra, and L. Hemaspaandra.
Multimode control attacks on elections.
Journal of Artificial Intelligence Research, 40:305–351, 2011.
5
P. Faliszewski and L. Hemaspaandra.
The consequences of eliminating NP solutions.
Computer Science Review, 2(1):40–54, 2008.
6
E. Hemaspaandra, L. Hemaspaandra, and H. Hempel.
An introduction to query order.
Bulletin of the EATCS, 63:93–107, 1997.
7
E. Hemaspaandra, L. Hemaspaandra, and H. Hempel.
Query order in the polynomial hierarchy.
Journal of Universal Computer Science, 4(6):574–588, 1998.
8
E. Hemaspaandra, L. Hemaspaandra, and H. Hempel.
R ${}^{{\cal S}{\cal N}}_{1\hbox{-}tt}$(NP) distinguishes robust many-one and Turing completeness.
Theory of Computing Systems, 31(3):307–325, 1998.
9
E. Hemaspaandra, L. Hemaspaandra, and H. Hempel.
What's up with downward collapse: Using the easy-hard technique to link boolean and polynomial hierarchy collapses.
SIGACT News, 29(3):10–22, 1998.
10
E. Hemaspaandra, L. Hemaspaandra, and H. Hempel.
A downward collapse within the polynomial hierarchy.
SIAM Journal on Computing, 28(2):383–393, 1999.
11
E. Hemaspaandra, L. Hemaspaandra, and H. Hempel.
Using the no-search easy-hard technique for downward collapse.
Technical Report TR-752, Department of Computer Science, University of Rochester, Rochester, NY, June 2001.
12
E. Hemaspaandra, L. Hemaspaandra, and H. Hempel.
Extending downward collapse from 1-versus-2 queries to $m$-versus-$m+1$ queries.
SIAM Journal on Computing, 34(6):1352–1369, 2005.
13
E. Hemaspaandra, L. Hemaspaandra, H. Spakowski, and O. Watanabe.
The robustness of LWPP and WPP, with an application to graph reconstruction.
In Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science, pages 51:1–51:14. Leibniz International Proceedings in Informatics (LIPIcs) #117, August 2018.
14
E. Hemaspaandra, L. Hemaspaandra, H. Spakowski, and O. Watanabe.
The robustness of LWPP and WPP, with an application to graph reconstruction.
Computational Complexity, 29(2, Article 7):1–49, 2020.
15
L. Hemaspaandra.
Beautiful structures: An appreciation of the contributions of Alan Selman.
SIGACT News, 45(3):54–70, 2014.
16
L. Hemaspaandra, H. Hempel, and G. Wechsung.
Query order.
SIAM Journal on Computing, 28(2):637–651, 1999.
17
L. Hemaspaandra and S. Jha.
Defying upward and downward separation.
Information and Computation, 121(1):1–13, 1995.
18
L. Hemaspaandra, M. Ogihara, and G. Wechsung.
Reducing the number of solutions of NP functions.
Journal of Computer and System Sciences, 64(2):311–328, 2002.
19
L. Hemaspaandra and R. Williams.
An atypical survey of typical-case heuristic algorithms.
SIGACT News, 43(4):71–89, 2012.
$\begin{tabular}{l}
{}~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\\
\hline
\end{tabular}$

(Last modified: February 16, 2023.)


Lane A. Hemaspaandra