10 Search Results for "Hitchcock, John M."

Document
DOI: 10.4230/LIPIcs.STACS.2026.75
Effective Versions of Strong Measure Zero

Authors: Matthew Rayman

Published in: LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Abstract
Effective versions of strong measure zero sets are developed for various levels of complexity and computability. It is shown that the sets can be equivalently defined using a generalization of supermartingales called odds supermartingales, success rates on supermartingales, predictors, and coverings. We show Borel’s conjecture that a set has strong measure zero if and only if it is countable holds in the time and space bounded setting. At the level of computability this does not hold. We show the computable level contains sequences at arbitrary levels of the hyperarithmetical hierarchy. This is done by proving a correspondence principle yielding a condition for the sets of computable strong measure zero to agree with the classical sets of strong measure zero. An algorithmic version of strong measure zero using lower semicomputability is defined. We show that this notion is equivalent to the set of NCR reals studied by Reimann and Slaman, thereby giving new characterizations of this set. Effective strong packing dimension zero is investigated by requiring success with respect to the limit inferior instead of the limit superior. It is proven that every sequence in the corresponding algorithmic class is decidable. At the level of computability, the sets coincide with a notion of weak countability that we define.
Cite as

Matthew Rayman. Effective Versions of Strong Measure Zero. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 75:1-75:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{rayman:LIPIcs.STACS.2026.75,
  author =	{Rayman, Matthew},
  title =	{{Effective Versions of Strong Measure Zero}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{75:1--75:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.75},
  URN =		{urn:nbn:de:0030-drops-255648},
  doi =		{10.4230/LIPIcs.STACS.2026.75},
  annote =	{Keywords: Strong measure zero, NCR, Effective fractal dimensions, Borel’s Conjecture, Hausdorff dimension, Packing dimension}
}
Document
DOI: 10.4230/LIPIcs.STACS.2026.52
Upper and Lower Bounds for the Linear Ordering Principle

Authors: Edward A. Hirsch and Ilya Volkovich

Published in: LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Abstract
Korten and Pitassi (FOCS, 2024) defined a new complexity class L₂^P as the polynomial-time Turing closure of the Linear Ordering Principle (a total function extending finding the minimum of an order [M. Chiari and J. Krajíček, 1998] to the case where the order is not linear). They put it between MA (Merlin-Arthur protocols) and S₂^P (the second symmetric level of the polynomial hierarchy). In this paper we sandwich L₂^P between P^prMA and P^prSBP. (The oracles here are promise problems, and SBP is the only known class between MA and AM.) The containment in P^prSBP is proved via an iterative process that uses a prSBP oracle to estimate the average order rank of a subset and find the minimum of a linear order. Another containment result of this paper is P^prO₂^P ⊆ O₂^P (where O₂^P is the input-oblivious version of S₂^P). These containment results altogether have several byproducts: - We give an affirmative answer to an open question posed by Chakaravarthy and Roy (Computational Complexity, 2011) whether P^prMA ⊆ S₂^P, thereby settling the relative standing of the existing (non-oblivious) Karp–Lipton–style collapse results of [V. T. Chakaravarthy and S. Roy, 2011] and [J.-Y. Cai, 2007], - We give an affirmative answer to an open question of Korten and Pitassi whether a Karp-Lipton-style collapse can be proven for L₂^P, - We show that the Karp-Lipton-style collapse to P^prOMA is actually better than both known collapses to P^prMA due to Chakaravarthy and Roy (Computational Complexity, 2011) and to O₂^P also due to Chakaravarthy and Roy (STACS, 2006). Thus we resolve the controversy between previously incomparable Karp-Lipton collapses stemming from these two lines of research.
Cite as

Edward A. Hirsch and Ilya Volkovich. Upper and Lower Bounds for the Linear Ordering Principle. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 52:1-52:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{hirsch_et_al:LIPIcs.STACS.2026.52,
  author =	{Hirsch, Edward A. and Volkovich, Ilya},
  title =	{{Upper and Lower Bounds for the Linear Ordering Principle}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{52:1--52:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.52},
  URN =		{urn:nbn:de:0030-drops-255410},
  doi =		{10.4230/LIPIcs.STACS.2026.52},
  annote =	{Keywords: Complexity Classes, Structural Complexity Theory, Linear Ordering Principle, Symmetric Alternation, Merlin-Arthur Protocols, Karp-Lipton Collapse}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.IPEC.2025.1
A Brief History of Parameterized Algorithms for Block-Structured Integer Programs (Invited Talk)

Authors: Martin Koutecký

Published in: LIPIcs, Volume 358, 20th International Symposium on Parameterized and Exact Computation (IPEC 2025)

Abstract
Integer Programming (IP) is a fundamental but computationally hard problem. Still, certain efficiently solvable subclasses have been identified over time, most notably totally unimodular IPs in the 1950s, and fixed-dimension IPs in the 1980s. Starting around the year 2000, a stream of research has identified block-structured IPs as yet another tractable subclass. In this paper, we give a brief and incomplete review of this history, with a focus on several of the author’s contributions.
Cite as

Martin Koutecký. A Brief History of Parameterized Algorithms for Block-Structured Integer Programs (Invited Talk). In 20th International Symposium on Parameterized and Exact Computation (IPEC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 358, pp. 1:1-1:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{koutecky:LIPIcs.IPEC.2025.1,
  author =	{Kouteck\'{y}, Martin},
  title =	{{A Brief History of Parameterized Algorithms for Block-Structured Integer Programs}},
  booktitle =	{20th International Symposium on Parameterized and Exact Computation (IPEC 2025)},
  pages =	{1:1--1:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-407-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{358},
  editor =	{Agrawal, Akanksha and van Leeuwen, Erik Jan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2025.1},
  URN =		{urn:nbn:de:0030-drops-251338},
  doi =		{10.4230/LIPIcs.IPEC.2025.1},
  annote =	{Keywords: Integer Programming, Parameterized Algorithm, Graver Basis, Treedepth, n-fold, tree-fold, 2-stage stochastic, multistage stochastic, Mixed-Integer Programming}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2025.58
Random Permutations in Computational Complexity

Authors: John M. Hitchcock, Adewale Sekoni, and Hadi Shafei

Published in: LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)

Abstract
Classical results of Bennett and Gill (1981) show that with probability 1, 𝖯^A ≠ NP^A relative to a random oracle A, and with probability 1, 𝖯^π ≠ NP^π ∩ coNP^π relative to a random permutation π. Whether 𝖯^A = NP^A ∩ coNP^A holds relative to a random oracle A remains open. While the random oracle separation has been extended to specific individually random oracles-such as Martin-Löf random or resource-bounded random oracles-no analogous result is known for individually random permutations. We introduce a new resource-bounded measure framework for analyzing individually random permutations. We define permutation martingales and permutation betting games that characterize measure-zero sets in the space of permutations, enabling formal definitions of polynomial-time random permutations, polynomial-time betting-game random permutations, and polynomial-space random permutations. Our main result shows that 𝖯^π ≠ NP^π ∩ coNP^π for every polynomial-time betting-game random permutation π. This is the first separation result relative to individually random permutations, rather than an almost-everywhere separation. We also strengthen a quantum separation of Bennett, Bernstein, Brassard, and Vazirani (1997) by showing that NP^π ∩ coNP^π ̸ ⊆ BQP^π for every polynomial-space random permutation π. We investigate the relationship between random permutations and random oracles. We prove that random oracles are polynomial-time reducible from random permutations. The converse-whether every random permutation is reducible from a random oracle-remains open. We show that if NP ∩ coNP is not a measurable subset of EXP, then 𝖯^A ≠ NP^A ∩ coNP^A holds with probability 1 relative to a random oracle A. Conversely, establishing this random oracle separation with time-bounded measure would imply BPP is a measure 0 subset of EXP. Our framework builds a foundation for studying permutation-based complexity using resource-bounded measure, in direct analogy to classical work on random oracles. It raises natural questions about the power and limitations of random permutations, their relationship to random oracles, and whether individual randomness can yield new class separations.
Cite as

John M. Hitchcock, Adewale Sekoni, and Hadi Shafei. Random Permutations in Computational Complexity. In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 345, pp. 58:1-58:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{hitchcock_et_al:LIPIcs.MFCS.2025.58,
  author =	{Hitchcock, John M. and Sekoni, Adewale and Shafei, Hadi},
  title =	{{Random Permutations in Computational Complexity}},
  booktitle =	{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
  pages =	{58:1--58:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-388-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{345},
  editor =	{Gawrychowski, Pawe{\l} and Mazowiecki, Filip and Skrzypczak, Micha{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.58},
  URN =		{urn:nbn:de:0030-drops-241652},
  doi =		{10.4230/LIPIcs.MFCS.2025.58},
  annote =	{Keywords: resource-bounded measure, martingales, betting games, random permutations, random oracles}
}
Document
DOI: 10.4230/LIPIcs.CCC.2025.20
Counting Martingales for Measure and Dimension in Complexity Classes

Authors: John M. Hitchcock, Adewale Sekoni, and Hadi Shafei

Published in: LIPIcs, Volume 339, 40th Computational Complexity Conference (CCC 2025)

Abstract
This paper makes two primary contributions. First, we introduce the concept of counting martingales and use it to define counting measures and counting dimensions. Second, we apply these new tools to strengthen previous circuit lower bounds. Resource-bounded measure and dimension have traditionally focused on deterministic time and space bounds. We use counting complexity classes to develop resource-bounded counting measures and dimensions. Counting martingales are constructed using functions from the #𝖯, SpanP, and GapP complexity classes. We show that counting martingales capture many martingale constructions in complexity theory. The resulting counting measures and dimensions are intermediate in power between the standard time-bounded and space-bounded notions, enabling finer-grained analysis where space-bounded measures are known, but time-bounded measures remain open. For example, we show that BPP has #𝖯-dimension 0 and BQP has GapP-dimension 0, whereas the 𝖯-dimensions of these classes remain open. As our main application, we improve circuit-size lower bounds. Lutz (1992) strengthened Shannon’s classic (1-ε) 2ⁿ/n lower bound (1949) to PSPACE-measure, showing that almost all problems require circuits of size (2ⁿ/n)(1+(α log n)/n), for any α < 1. We extend this result to SpanP-measure, with a proof that uses a connection through the Minimum Circuit Size Problem (MCSP) to construct a counting martingale. Our results imply that the stronger lower bound holds within the third level of the exponential-time hierarchy, whereas previously, it was only known in ESPACE. Under a derandomization hypothesis, this lower bound holds within the second level of the exponential-time hierarchy, specifically in the class 𝖤^NP. We also study the #𝖯-dimension of classical circuit complexity classes and the GapP-dimension of quantum circuit complexity classes.
Cite as

John M. Hitchcock, Adewale Sekoni, and Hadi Shafei. Counting Martingales for Measure and Dimension in Complexity Classes. In 40th Computational Complexity Conference (CCC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 339, pp. 20:1-20:35, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{hitchcock_et_al:LIPIcs.CCC.2025.20,
  author =	{Hitchcock, John M. and Sekoni, Adewale and Shafei, Hadi},
  title =	{{Counting Martingales for Measure and Dimension in Complexity Classes}},
  booktitle =	{40th Computational Complexity Conference (CCC 2025)},
  pages =	{20:1--20:35},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-379-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{339},
  editor =	{Srinivasan, Srikanth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2025.20},
  URN =		{urn:nbn:de:0030-drops-237145},
  doi =		{10.4230/LIPIcs.CCC.2025.20},
  annote =	{Keywords: resource-bounded measure, resource-bounded dimension, counting martingales, counting complexity, circuit complexity, Kolmogorov complexity, quantum complexity, Minimum Circuit Size Problem}
}
Document
DOI: 10.4230/LIPIcs.STACS.2018.40
Nonuniform Reductions and NP-Completeness

Authors: John M. Hitchcock and Hadi Shafei

Published in: LIPIcs, Volume 96, 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)

Abstract
Nonuniformity is a central concept in computational complexity with powerful connections to circuit complexity and randomness. Nonuniform reductions have been used to study the isomorphism conjecture for NP and completeness for larger complexity classes. We study the power of nonuniform reductions for NP0completeness, obtaining both separations and upper bounds for nonuniform completeness vs uniform complessness in NP. Under various hypotheses, we obtain the following separations: 1. There is a set complete for NP under nonuniform many-one reductions, but not under uniform many-one reductions. This is true even with a single bit of nonuniform advice. 2. There is a set complete for NP under nonuniform many-one reductions with polynomial-size advice, but not under uniform Turing reductions. That is, polynomial nonuniformity is stronger than a polynomial number of queries. 3. For any fixed polynomial p(n), there is a set complete for NP under uniform 2-truth-table reductions, but not under nonuniform many-one reductions that use p(n) advice. That is, giving a uniform reduction a second query makes it more powerful than a nonuniform reduction with fixed polynomial advice. 4. There is a set complete for NP under nonuniform many-one reductions with polynomial ad- vice, but not under nonuniform many-one reductions with logarithmic advice. This hierarchy theorem also holds for other reducibilities, such as truth-table and Turing. We also consider uniform upper bounds on nonuniform completeness. Hirahara (2015) showed that unconditionally every set that is complete for NP under nonuniform truth-table reductions that use logarithmic advice is also uniformly Turing-complete. We show that under a derandomization hypothesis, the same statement for truth-table reductions and truth-table completeness also holds.
Cite as

John M. Hitchcock and Hadi Shafei. Nonuniform Reductions and NP-Completeness. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 96, pp. 40:1-40:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{hitchcock_et_al:LIPIcs.STACS.2018.40,
  author =	{Hitchcock, John M. and Shafei, Hadi},
  title =	{{Nonuniform Reductions and NP-Completeness}},
  booktitle =	{35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)},
  pages =	{40:1--40:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-062-0},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{96},
  editor =	{Niedermeier, Rolf and Vall\'{e}e, Brigitte},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2018.40},
  URN =		{urn:nbn:de:0030-drops-85217},
  doi =		{10.4230/LIPIcs.STACS.2018.40},
  annote =	{Keywords: computational complexity, NP-completeness, reducibility, nonuniform complexity}
}
Document
DOI: 10.4230/LIPIcs.STACS.2016.42
Autoreducibility of NP-Complete Sets

Authors: John M. Hitchcock and Hadi Shafei

Published in: LIPIcs, Volume 47, 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)

Abstract
We study the polynomial-time autoreducibility of NP-complete sets and obtain separations under strong hypotheses for NP. Assuming there is a p-generic set in NP, we show the following: - For every k >= 2, there is a k-T-complete set for NP that is k-T autoreducible, but is not k-tt autoreducible or (k-1)-T autoreducible. - For every k >= 3, there is a k-tt-complete set for NP that is k-tt autoreducible, but is not (k-1)-tt autoreducible or (k-2)-T autoreducible. - There is a tt-complete set for NP that is tt-autoreducible, but is not btt-autoreducible. Under the stronger assumption that there is a p-generic set in NP cap coNP, we show: - For every k >= 2, there is a k-tt-complete set for NP that is k-tt autoreducible, but is not (k-1)-T autoreducible. Our proofs are based on constructions from separating NP-completeness notions. For example, the construction of a 2-T-complete set for NP that is not 2-tt-complete also separates 2-T-autoreducibility from 2-tt-autoreducibility.
Cite as

John M. Hitchcock and Hadi Shafei. Autoreducibility of NP-Complete Sets. In 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 47, pp. 42:1-42:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{hitchcock_et_al:LIPIcs.STACS.2016.42,
  author =	{Hitchcock, John M. and Shafei, Hadi},
  title =	{{Autoreducibility of NP-Complete Sets}},
  booktitle =	{33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)},
  pages =	{42:1--42:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-001-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{47},
  editor =	{Ollinger, Nicolas and Vollmer, Heribert},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2016.42},
  URN =		{urn:nbn:de:0030-drops-57437},
  doi =		{10.4230/LIPIcs.STACS.2016.42},
  annote =	{Keywords: computational complexity, NP-completeness, autoreducibility, genericity}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2015.236
On the NP-Completeness of the Minimum Circuit Size Problem

Authors: John M. Hitchcock and A. Pavan

Published in: LIPIcs, Volume 45, 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)

Abstract
We study the Minimum Circuit Size Problem (MCSP): given the truth-table of a Boolean function f and a number k, does there exist a Boolean circuit of size at most k computing f? This is a fundamental NP problem that is not known to be NP-complete. Previous work has studied consequences of the NP-completeness of MCSP. We extend this work and consider whether MCSP may be complete for NP under more powerful reductions. We also show that NP-completeness of MCSP allows for amplification of circuit complexity. We show the following results. - If MCSP is NP-complete via many-one reductions, the following circuit complexity amplification result holds: If NP cap co-NP requires 2^n^{Omega(1)-size circuits, then E^NP requires 2^Omega(n)-size circuits. - If MCSP is NP-complete under truth-table reductions, then EXP neq NP cap SIZE(2^n^epsilon) for some epsilon> 0 and EXP neq ZPP. This result extends to polylog Turing reductions.
Cite as

John M. Hitchcock and A. Pavan. On the NP-Completeness of the Minimum Circuit Size Problem. In 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 45, pp. 236-245, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{hitchcock_et_al:LIPIcs.FSTTCS.2015.236,
  author =	{Hitchcock, John M. and Pavan, A.},
  title =	{{On the NP-Completeness of the Minimum Circuit Size Problem}},
  booktitle =	{35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)},
  pages =	{236--245},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-97-2},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{45},
  editor =	{Harsha, Prahladh and Ramalingam, G.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2015.236},
  URN =		{urn:nbn:de:0030-drops-56613},
  doi =		{10.4230/LIPIcs.FSTTCS.2015.236},
  annote =	{Keywords: Minimum Circuit Size, NP-completeness, truth-table reductions, circuit complexity}
}
Document
DOI: 10.4230/LIPIcs.STACS.2010.2462
Collapsing and Separating Completeness Notions under Average-Case and Worst-Case Hypotheses

Authors: Xiaoyang Gu, John M. Hitchcock, and Aduri Pavan

Published in: LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010)

Abstract
This paper presents the following results on sets that are complete for $\NP$. \begin{enumerate} \item If there is a problem in $\NP$ that requires $\twonO$ time at almost all lengths, then every many-one NP-complete set is complete under length-increasing reductions that are computed by polynomial-size circuits. \item If there is a problem in $\CoNP$ that cannot be solved by polynomial-size nondeterministic circuits, then every many-one complete set is complete under length-increasing reductions that are computed by polynomial-size circuits. \item If there exist a one-way permutation that is secure against subexponential-size circuits and there is a hard tally language in $\NP \cap \CoNP$, then there is a Turing complete language for $\NP$ that is not many-one complete. \end{enumerate} Our first two results use worst-case hardness hypotheses whereas earlier work that showed similar results relied on average-case or almost-everywhere hardness assumptions. The use of average-case and worst-case hypotheses in the last result is unique as previous results obtaining the same consequence relied on almost-everywhere hardness results.
Cite as

Xiaoyang Gu, John M. Hitchcock, and Aduri Pavan. Collapsing and Separating Completeness Notions under Average-Case and Worst-Case Hypotheses. In 27th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 5, pp. 429-440, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{gu_et_al:LIPIcs.STACS.2010.2462,
  author =	{Gu, Xiaoyang and Hitchcock, John M. and Pavan, Aduri},
  title =	{{Collapsing and Separating Completeness Notions under Average-Case and Worst-Case Hypotheses}},
  booktitle =	{27th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{429--440},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-16-3},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{5},
  editor =	{Marion, Jean-Yves and Schwentick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010.2462},
  URN =		{urn:nbn:de:0030-drops-24627},
  doi =		{10.4230/LIPIcs.STACS.2010.2462},
  annote =	{Keywords: Computational complexity, NP-completeness}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2009.2320
Kolmogorov Complexity in Randomness Extraction

Authors: John M. Hitchcock, Aduri Pavan, and N. V. Vinodchandran

Published in: LIPIcs, Volume 4, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2009)

Abstract
We clarify the role of Kolmogorov complexity in the area of randomness extraction. We show that a computable function is an almost randomness extractor if and only if it is a Kolmogorov complexity extractor, thus establishing a fundamental equivalence between two forms of extraction studied in the literature: Kolmogorov extraction and randomness extraction. We present a distribution ${\cal M}_k$ based on Kolmogorov complexity that is complete for randomness extraction in the sense that a computable function is an almost randomness extractor if and only if it extracts randomness from ${\cal M}_k$.
Cite as

John M. Hitchcock, Aduri Pavan, and N. V. Vinodchandran. Kolmogorov Complexity in Randomness Extraction. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 4, pp. 215-226, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{hitchcock_et_al:LIPIcs.FSTTCS.2009.2320,
  author =	{Hitchcock, John M. and Pavan, Aduri and Vinodchandran, N. V.},
  title =	{{Kolmogorov Complexity in Randomness Extraction}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science},
  pages =	{215--226},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-13-2},
  ISSN =	{1868-8969},
  year =	{2009},
  volume =	{4},
  editor =	{Kannan, Ravi and Narayan Kumar, K.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2009.2320},
  URN =		{urn:nbn:de:0030-drops-23201},
  doi =		{10.4230/LIPIcs.FSTTCS.2009.2320},
  annote =	{Keywords: Extractors, Kolmogorov extractors, randomness}
}
  • Refine by Type
  • 10 Document/PDF
  • 5 Document/HTML

  • Refine by Publication Year
  • 2 2026
  • 3 2025
  • 1 2018
  • 1 2016
  • 1 2015
  • Show More...

  • Refine by Author
  • 7 Hitchcock, John M.
  • 4 Shafei, Hadi
  • 2 Pavan, Aduri
  • 2 Sekoni, Adewale
  • 1 Gu, Xiaoyang
  • Show More...

  • Refine by Series/Journal
  • 10 LIPIcs

  • Refine by Classification
  • 3 Theory of computation → Complexity classes
  • 2 Theory of computation → Circuit complexity
  • 2 Theory of computation → Computational complexity and cryptography
  • 2 Theory of computation → Quantum complexity theory
  • 1 Theory of computation
  • Show More...

  • Refine by Keyword
  • 4 NP-completeness
  • 2 circuit complexity
  • 2 computational complexity
  • 2 resource-bounded measure
  • 1 2-stage stochastic
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact