Downward Collapses and 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?
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 ) the issue of whether the 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.
- 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
(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
-versus- 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.
(Last modified: February 16, 2023.)
Lane A. Hemaspaandra
|