30 Search Results for "Hirahara, Shuichi"


Document
Total NP Search Problems with Abundant Solutions

Authors: Jiawei Li

Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)


Abstract
We define a new complexity class TFAP to capture TFNP problems that possess abundant solutions for each input. We identify several problems across diverse fields that belong to TFAP, including WeakPigeon (finding a collision in a mapping from [2n] pigeons to [n] holes), Yamakawa-Zhandry’s problem [Takashi Yamakawa and Mark Zhandry, 2022], and all problems in TFZPP. Conversely, we introduce the notion of "semi-gluability" to characterize TFNP problems that could have a unique or a very limited number of solutions for certain inputs. We prove that there is no black-box reduction from any "semi-gluable" problems to any TFAP problems. Furthermore, it can be extended to rule out randomized black-box reduction in most cases. We identify that the majority of common TFNP subclasses, including PPA, PPAD, PPADS, PPP, PLS, CLS, SOPL, and UEOPL, are "semi-gluable". This leads to a broad array of oracle separation results within TFNP regime. As a corollary, UEOPL^O ⊈ PWPP^O relative to an oracle O.

Cite as

Jiawei Li. Total NP Search Problems with Abundant Solutions. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 75:1-75:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)


Copy BibTex To Clipboard

@InProceedings{li:LIPIcs.ITCS.2024.75,
  author =	{Li, Jiawei},
  title =	{{Total NP Search Problems with Abundant Solutions}},
  booktitle =	{15th Innovations in Theoretical Computer Science Conference (ITCS 2024)},
  pages =	{75:1--75:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-309-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{287},
  editor =	{Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.75},
  URN =		{urn:nbn:de:0030-drops-196031},
  doi =		{10.4230/LIPIcs.ITCS.2024.75},
  annote =	{Keywords: TFNP, Pigeonhole Principle}
}
Document
Regularization of Low Error PCPs and an Application to MCSP

Authors: Shuichi Hirahara and Dana Moshkovitz

Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)


Abstract
In a regular PCP the verifier queries each proof symbol in the same number of tests. This number is called the degree of the proof, and it is at least 1/(sq) where s is the soundness error and q is the number of queries. It is incredibly useful to have regularity and reduced degree in PCP. There is an expander-based transformation by Papadimitriou and Yannakakis that transforms any PCP with a constant number of queries and constant soundness error to a regular PCP with constant degree. There are also transformations for low error projection and unique PCPs. Other PCPs are constructed especially to be regular. In this work we show how to regularize and reduce degree of PCPs with a possibly large number of queries and low soundness error. As an application, we prove NP-hardness of an unweighted variant of the collective minimum monotone satisfying assignment problem, which was introduced by Hirahara (FOCS'22) to prove NP-hardness of MCSP^* (the partial function variant of the Minimum Circuit Size Problem) under randomized reductions. We present a simplified proof and sufficient conditions under which MCSP^* is NP-hard under the standard notion of reduction: MCSP^* is NP-hard under deterministic polynomial-time many-one reductions if there exists a function in E that satisfies certain direct sum properties.

Cite as

Shuichi Hirahara and Dana Moshkovitz. Regularization of Low Error PCPs and an Application to MCSP. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 39:1-39:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{hirahara_et_al:LIPIcs.ISAAC.2023.39,
  author =	{Hirahara, Shuichi and Moshkovitz, Dana},
  title =	{{Regularization of Low Error PCPs and an Application to MCSP}},
  booktitle =	{34th International Symposium on Algorithms and Computation (ISAAC 2023)},
  pages =	{39:1--39:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-289-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{283},
  editor =	{Iwata, Satoru and Kakimura, Naonori},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.39},
  URN =		{urn:nbn:de:0030-drops-193411},
  doi =		{10.4230/LIPIcs.ISAAC.2023.39},
  annote =	{Keywords: PCP theorem, regularization, Minimum Circuit Size Problem}
}
Document
Bounded Relativization

Authors: Shuichi Hirahara, Zhenjian Lu, and Hanlin Ren

Published in: LIPIcs, Volume 264, 38th Computational Complexity Conference (CCC 2023)


Abstract
Relativization is one of the most fundamental concepts in complexity theory, which explains the difficulty of resolving major open problems. In this paper, we propose a weaker notion of relativization called bounded relativization. For a complexity class ℭ, we say that a statement is ℭ-relativizing if the statement holds relative to every oracle 𝒪 ∈ ℭ. It is easy to see that every result that relativizes also ℭ-relativizes for every complexity class ℭ. On the other hand, we observe that many non-relativizing results, such as IP = PSPACE, are in fact PSPACE-relativizing. First, we use the idea of bounded relativization to obtain new lower bound results, including the following nearly maximum circuit lower bound: for every constant ε > 0, BPE^{MCSP}/2^{εn} ⊈ SIZE[2ⁿ/n]. We prove this by PSPACE-relativizing the recent pseudodeterministic pseudorandom generator by Lu, Oliveira, and Santhanam (STOC 2021). Next, we study the limitations of PSPACE-relativizing proof techniques, and show that a seemingly minor improvement over the known results using PSPACE-relativizing techniques would imply a breakthrough separation NP ≠ L. For example: - Impagliazzo and Wigderson (JCSS 2001) proved that if EXP ≠ BPP, then BPP admits infinitely-often subexponential-time heuristic derandomization. We show that their result is PSPACE-relativizing, and that improving it to worst-case derandomization using PSPACE-relativizing techniques implies NP ≠ L. - Oliveira and Santhanam (STOC 2017) recently proved that every dense subset in P admits an infinitely-often subexponential-time pseudodeterministic construction, which we observe is PSPACE-relativizing. Improving this to almost-everywhere (pseudodeterministic) or (infinitely-often) deterministic constructions by PSPACE-relativizing techniques implies NP ≠ L. - Santhanam (SICOMP 2009) proved that pr-MA does not have fixed polynomial-size circuits. This lower bound can be shown PSPACE-relativizing, and we show that improving it to an almost-everywhere lower bound using PSPACE-relativizing techniques implies NP ≠ L. In fact, we show that if we can use PSPACE-relativizing techniques to obtain the above-mentioned improvements, then PSPACE ≠ EXPH. We obtain our barrier results by constructing suitable oracles computable in EXPH relative to which these improvements are impossible.

Cite as

Shuichi Hirahara, Zhenjian Lu, and Hanlin Ren. Bounded Relativization. In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 6:1-6:45, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{hirahara_et_al:LIPIcs.CCC.2023.6,
  author =	{Hirahara, Shuichi and Lu, Zhenjian and Ren, Hanlin},
  title =	{{Bounded Relativization}},
  booktitle =	{38th Computational Complexity Conference (CCC 2023)},
  pages =	{6:1--6:45},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-282-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{264},
  editor =	{Ta-Shma, Amnon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2023.6},
  URN =		{urn:nbn:de:0030-drops-182764},
  doi =		{10.4230/LIPIcs.CCC.2023.6},
  annote =	{Keywords: relativization, circuit lower bound, derandomization, explicit construction, pseudodeterministic algorithms, interactive proofs}
}
Document
Improved Learning from Kolmogorov Complexity

Authors: Halley Goldberg and Valentine Kabanets

Published in: LIPIcs, Volume 264, 38th Computational Complexity Conference (CCC 2023)


Abstract
Carmosino, Impagliazzo, Kabanets, and Kolokolova (CCC, 2016) showed that the existence of natural properties in the sense of Razborov and Rudich (JCSS, 1997) implies PAC learning algorithms in the sense of Valiant (Comm. ACM, 1984), for boolean functions in P/poly, under the uniform distribution and with membership queries. It is still an open problem to get from natural properties learning algorithms that do not rely on membership queries but rather use randomly drawn labeled examples. Natural properties may be understood as an average-case version of MCSP, the problem of deciding the minimum size of a circuit computing a given truth-table. Problems related to MCSP include those concerning time-bounded Kolmogorov complexity. MKTP, for example, asks for the KT-complexity of a given string. KT-complexity is a relaxation of circuit size, as it does away with the requirement that a short description of a string be interpreted as a boolean circuit. In this work, under assumptions of MKTP and the related problem MK^tP being easy on average, we get learning algorithms for boolean functions in P/poly that - work over any distribution D samplable by a family of polynomial-size circuits (given explicitly in the case of MKTP), - only use randomly drawn labeled examples from D, and - are agnostic (do not require the target function to belong to the hypothesis class). Our results build upon the recent work of Hirahara and Nanashima (FOCS, 2021) who showed similar learning consequences but under a stronger assumption that NP is easy on average.

Cite as

Halley Goldberg and Valentine Kabanets. Improved Learning from Kolmogorov Complexity. In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 12:1-12:29, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{goldberg_et_al:LIPIcs.CCC.2023.12,
  author =	{Goldberg, Halley and Kabanets, Valentine},
  title =	{{Improved Learning from Kolmogorov Complexity}},
  booktitle =	{38th Computational Complexity Conference (CCC 2023)},
  pages =	{12:1--12:29},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-282-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{264},
  editor =	{Ta-Shma, Amnon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2023.12},
  URN =		{urn:nbn:de:0030-drops-182825},
  doi =		{10.4230/LIPIcs.CCC.2023.12},
  annote =	{Keywords: learning, Kolmogorov complexity, meta-complexity, average-case complexity}
}
Document
Kolmogorov Complexity Characterizes Statistical Zero Knowledge

Authors: Eric Allender, Shuichi Hirahara, and Harsha Tirumala

Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)


Abstract
We show that a decidable promise problem has a non-interactive statistical zero-knowledge proof system if and only if it is randomly reducible via an honest polynomial-time reduction to a promise problem for Kolmogorov-random strings, with a superlogarithmic additive approximation term. This extends recent work by Saks and Santhanam (CCC 2022). We build on this to give new characterizations of Statistical Zero Knowledge SZK, as well as the related classes NISZK_L and SZK_L.

Cite as

Eric Allender, Shuichi Hirahara, and Harsha Tirumala. Kolmogorov Complexity Characterizes Statistical Zero Knowledge. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 3:1-3:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{allender_et_al:LIPIcs.ITCS.2023.3,
  author =	{Allender, Eric and Hirahara, Shuichi and Tirumala, Harsha},
  title =	{{Kolmogorov Complexity Characterizes Statistical Zero Knowledge}},
  booktitle =	{14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
  pages =	{3:1--3:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-263-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{251},
  editor =	{Tauman Kalai, Yael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.3},
  URN =		{urn:nbn:de:0030-drops-175063},
  doi =		{10.4230/LIPIcs.ITCS.2023.3},
  annote =	{Keywords: Kolmogorov Complexity, Interactive Proofs}
}
Document
Learning Versus Pseudorandom Generators in Constant Parallel Time

Authors: Shuichi Hirahara and Mikito Nanashima

Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)


Abstract
A polynomial-stretch pseudorandom generator (PPRG) in NC⁰ (i.e., constant parallel time) is one of the most important cryptographic primitives, especially for constructing highly efficient cryptography and indistinguishability obfuscation. The celebrated work (Applebaum, Ishai, and Kushilevitz, SIAM Journal on Computing, 2006) on randomized encodings yields the characterization of sublinear-stretch pseudorandom generators in NC⁰ by the existence of logspace-computable one-way functions, but characterizing PPRGs in NC⁰ seems out of reach at present. Therefore, it is natural to ask which sort of hardness notion is essential for constructing PPRGs in NC⁰. Particularly, to the best of our knowledge, all the previously known candidates for PPRGs in NC⁰ follow only one framework based on Goldreich’s one-way function. In this paper, we present a new learning-theoretic characterization for PPRGs in NC⁰ and related classes. Specifically, we consider the average-case hardness of learning for well-studied classes in parameterized settings, where the number of samples is restricted to fixed-parameter tractable (FPT), and show that the following are equivalent: - The existence of (a collection of) PPRGs in NC⁰. - The average-case hardness of learning sparse 𝔽₂-polynomials on a sparse example distribution and an NC⁰-samplable target distribution (i.e., a distribution on target functions). - The average-case hardness of learning Fourier-sparse functions on a sparse example distribution and an NC⁰-samplable target distribution. - The average-case hardness of learning constant-depth parity decision trees on a sparse example distribution and an NC⁰-samplable target distribution. Furthermore, we characterize a (single) PPRG in parity-NC⁰ by the average-case hardness of learning constant-degree 𝔽₂-polynomials on a uniform example distribution with FPT samples. Based on our results, we propose new candidates for PPRGs in NC⁰ and related classes under a hardness assumption on a natural learning problem. An important property of PPRGs in NC⁰ constructed in our framework is that the output bits are computed by various predicates; thus, it seems to resist an attack that depends on a specific property of one fixed predicate. Conceptually, the main contribution of this study is to formalize a theory of FPT dualization of concept classes, which yields a meta-theorem for the first result. For the second result on PPRGs in parity-NC⁰, we use a different technique of pseudorandom 𝔽₂-polynomials.

Cite as

Shuichi Hirahara and Mikito Nanashima. Learning Versus Pseudorandom Generators in Constant Parallel Time. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 70:1-70:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{hirahara_et_al:LIPIcs.ITCS.2023.70,
  author =	{Hirahara, Shuichi and Nanashima, Mikito},
  title =	{{Learning Versus Pseudorandom Generators in Constant Parallel Time}},
  booktitle =	{14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
  pages =	{70:1--70:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-263-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{251},
  editor =	{Tauman Kalai, Yael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.70},
  URN =		{urn:nbn:de:0030-drops-175736},
  doi =		{10.4230/LIPIcs.ITCS.2023.70},
  annote =	{Keywords: Parallel cryptography, polynomial-stretch pseudorandom generators in NC⁰, PAC learning, average-case complexity, fixed-parameter tractability}
}
Document
Probabilistic Kolmogorov Complexity with Applications to Average-Case Complexity

Authors: Halley Goldberg, Valentine Kabanets, Zhenjian Lu, and Igor C. Oliveira

Published in: LIPIcs, Volume 234, 37th Computational Complexity Conference (CCC 2022)


Abstract
Understanding the relationship between the worst-case and average-case complexities of NP and of other subclasses of PH is a long-standing problem in complexity theory. Over the last few years, much progress has been achieved in this front through the investigation of meta-complexity: the complexity of problems that refer to the complexity of the input string x (e.g., given a string x, estimate its time-bounded Kolmogorov complexity). In particular, [Shuichi Hirahara, 2021] employed techniques from meta-complexity to show that if DistNP ⊆ AvgP then UP ⊆ DTIME[2^{O(n/log n)}]. While this and related results [Shuichi Hirahara and Mikito Nanashima, 2021; Lijie Chen et al., 2022] offer exciting progress after a long gap, they do not survive in the setting of randomized computations: roughly speaking, "randomness" is the opposite of "structure", and upper bounding the amount of structure (time-bounded Kolmogorov complexity) of different objects is crucial in recent applications of meta-complexity. This limitation is significant, since randomized computations are ubiquitous in algorithm design and give rise to a more robust theory of average-case complexity [Russell Impagliazzo and Leonid A. Levin, 1990]. In this work, we develop a probabilistic theory of meta-complexity, by incorporating randomness into the notion of complexity of a string x. This is achieved through a new probabilistic variant of time-bounded Kolmogorov complexity that we call pK^t complexity. Informally, pK^t(x) measures the complexity of x when shared randomness is available to all parties involved in a computation. By porting key results from meta-complexity to the probabilistic domain of pK^t complexity and its variants, we are able to establish new connections between worst-case and average-case complexity in the important setting of probabilistic computations: - If DistNP ⊆ AvgBPP, then UP ⊆ RTIME[2^O(n/log n)]. - If DistΣ^P_2 ⊆ AvgBPP, then AM ⊆ BPTIME[2^O(n/log n)]. - In the fine-grained setting [Lijie Chen et al., 2022], we get UTIME[2^O(√{nlog n})] ⊆ RTIME[2^O(√{nlog n})] and AMTIME[2^O(√{nlog n})] ⊆ BPTIME[2^O(√{nlog n})] from stronger average-case assumptions. - If DistPH ⊆ AvgBPP, then PH ⊆ BPTIME[2^O(n/log n)]. Specifically, for any 𝓁 ≥ 0, if DistΣ_{𝓁+2}^P ⊆ AvgBPP then Σ_𝓁^{P} ⊆ BPTIME[2^O(n/log n)]. - Strengthening a result from [Shuichi Hirahara and Mikito Nanashima, 2021], we show that if DistNP ⊆ AvgBPP then polynomial size Boolean circuits can be agnostically PAC learned under any unknown 𝖯/poly-samplable distribution in polynomial time. In some cases, our framework allows us to significantly simplify existing proofs, or to extend results to the more challenging probabilistic setting with little to no extra effort.

Cite as

Halley Goldberg, Valentine Kabanets, Zhenjian Lu, and Igor C. Oliveira. Probabilistic Kolmogorov Complexity with Applications to Average-Case Complexity. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 16:1-16:60, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{goldberg_et_al:LIPIcs.CCC.2022.16,
  author =	{Goldberg, Halley and Kabanets, Valentine and Lu, Zhenjian and Oliveira, Igor C.},
  title =	{{Probabilistic Kolmogorov Complexity with Applications to Average-Case Complexity}},
  booktitle =	{37th Computational Complexity Conference (CCC 2022)},
  pages =	{16:1--16:60},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-241-9},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{234},
  editor =	{Lovett, Shachar},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2022.16},
  URN =		{urn:nbn:de:0030-drops-165785},
  doi =		{10.4230/LIPIcs.CCC.2022.16},
  annote =	{Keywords: average-case complexity, Kolmogorov complexity, meta-complexity, worst-case to average-case reductions, learning}
}
Document
Finding Errorless Pessiland in Error-Prone Heuristica

Authors: Shuichi Hirahara and Mikito Nanashima

Published in: LIPIcs, Volume 234, 37th Computational Complexity Conference (CCC 2022)


Abstract
Average-case complexity has two standard formulations, i.e., errorless complexity and error-prone complexity. In average-case complexity, a critical topic of research is to show the equivalence between these formulations, especially on the average-case complexity of NP. In this study, we present a relativization barrier for such an equivalence. Specifically, we construct an oracle relative to which NP is easy on average in the error-prone setting (i.e., DistNP ⊆ HeurP) but hard on average in the errorless setting even by 2^o(n/log n)-size circuits (i.e., DistNP ⊈ AvgSIZE[2^o(n/log n)]), which provides an answer to the open question posed by Impagliazzo (CCC 2011). Additionally, we show the following in the same relativized world: - Lower bound of meta-complexity: GapMINKT^𝒪 ∉ prSIZE^𝒪[2^o(n/log n)] and GapMCSP^𝒪 ∉ prSIZE^𝒪[2^(n^ε)] for some ε > 0. - Worst-case hardness of learning on uniform distributions: P/poly is not weakly PAC learnable with membership queries on the uniform distribution by nonuniform 2ⁿ/n^ω(1)-time algorithms. - Average-case hardness of distribution-free learning: P/poly is not weakly PAC learnable on average by nonuniform 2^o(n/log n)-time algorithms. - Weak cryptographic primitives: There exist a hitting set generator, an auxiliary-input one-way function, an auxiliary-input pseudorandom generator, and an auxiliary-input pseudorandom function against SIZE^𝒪[2^o(n/log n)]. This provides considerable insights into Pessiland (i.e., the world in which no one-way function exists, and NP is hard on average), such as the relativized separation of the error-prone average-case hardness of NP and auxiliary-input cryptography. At the core of our oracle construction is a new notion of random restriction with masks.

Cite as

Shuichi Hirahara and Mikito Nanashima. Finding Errorless Pessiland in Error-Prone Heuristica. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 25:1-25:28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{hirahara_et_al:LIPIcs.CCC.2022.25,
  author =	{Hirahara, Shuichi and Nanashima, Mikito},
  title =	{{Finding Errorless Pessiland in Error-Prone Heuristica}},
  booktitle =	{37th Computational Complexity Conference (CCC 2022)},
  pages =	{25:1--25:28},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-241-9},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{234},
  editor =	{Lovett, Shachar},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2022.25},
  URN =		{urn:nbn:de:0030-drops-165875},
  doi =		{10.4230/LIPIcs.CCC.2022.25},
  annote =	{Keywords: average-case complexity, oracle separation, relativization barrier, meta-complexity, learning, auxiliary-input cryptography}
}
Document
Symmetry of Information from Meta-Complexity

Authors: Shuichi Hirahara

Published in: LIPIcs, Volume 234, 37th Computational Complexity Conference (CCC 2022)


Abstract
Symmetry of information for time-bounded Kolmogorov complexity is a hypothetical inequality that relates time-bounded Kolmogorov complexity and its conditional analogue. In 1992, Longpré and Watanabe showed that symmetry of information holds if NP is easy in the worst case, which has been the state of the art over the last three decades. In this paper, we significantly improve this result by showing that symmetry of information holds under the weaker assumption that NP is easy on average. In fact, our proof techniques are applicable to any resource-bounded Kolmogorov complexity and enable proving symmetry of information from an efficient algorithm that computes resource-bounded Kolmogorov complexity. We demonstrate the significance of our proof techniques by presenting two applications. First, using that symmetry of information does not hold for Levin’s Kt-complexity, we prove that randomized Kt-complexity cannot be computed in time 2^o(n) on inputs of length n, which improves the previous quasi-polynomial lower bound of Oliveira (ICALP 2019). Our proof implements Kolmogorov’s insightful approach to the P versus NP problem in the case of randomized Kt-complexity. Second, we consider the question of excluding Heuristica, i.e., a world in which NP is easy on average but NP ≠ P, from Impagliazzo’s five worlds: Using symmetry of information, we prove that Heuristica is excluded if the problem of approximating time-bounded conditional Kolmogorov complexity K^t(x∣y) up to some additive error is NP-hard for t ≫ |y|. We complement this result by proving NP-hardness of approximating sublinear-time-bounded conditional Kolmogorov complexity up to a multiplicative factor of |x|^{1/(log log |x|)^O(1)} for t ≪ |y|. Our NP-hardness proof presents a new connection between sublinear-time-bounded conditional Kolmogorov complexity and a secret sharing scheme.

Cite as

Shuichi Hirahara. Symmetry of Information from Meta-Complexity. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 26:1-26:41, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{hirahara:LIPIcs.CCC.2022.26,
  author =	{Hirahara, Shuichi},
  title =	{{Symmetry of Information from Meta-Complexity}},
  booktitle =	{37th Computational Complexity Conference (CCC 2022)},
  pages =	{26:1--26:41},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-241-9},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{234},
  editor =	{Lovett, Shachar},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2022.26},
  URN =		{urn:nbn:de:0030-drops-165880},
  doi =		{10.4230/LIPIcs.CCC.2022.26},
  annote =	{Keywords: resource-bounded Kolmogorov complexity, average-case complexity, pseudorandomness, hardness of approximation, unconditional lower bound}
}
Document
On Randomized Reductions to the Random Strings

Authors: Michael Saks and Rahul Santhanam

Published in: LIPIcs, Volume 234, 37th Computational Complexity Conference (CCC 2022)


Abstract
We study the power of randomized polynomial-time non-adaptive reductions to the problem of approximating Kolmogorov complexity and its polynomial-time bounded variants. As our first main result, we give a sharp dichotomy for randomized non-adaptive reducibility to approximating Kolmogorov complexity. We show that any computable language L that has a randomized polynomial-time non-adaptive reduction (satisfying a natural honesty condition) to ω(log(n))-approximating the Kolmogorov complexity is in AM ∩ coAM. On the other hand, using results of Hirahara [Shuichi Hirahara, 2020], it follows that every language in NEXP has a randomized polynomial-time non-adaptive reduction (satisfying the same honesty condition as before) to O(log(n))-approximating the Kolmogorov complexity. As our second main result, we give the first negative evidence against the NP-hardness of polynomial-time bounded Kolmogorov complexity with respect to randomized reductions. We show that for every polynomial t', there is a polynomial t such that if there is a randomized time t' non-adaptive reduction (satisfying a natural honesty condition) from SAT to ω(log(n))-approximating K^t complexity, then either NE = coNE or 𝖤 has sub-exponential size non-deterministic circuits infinitely often.

Cite as

Michael Saks and Rahul Santhanam. On Randomized Reductions to the Random Strings. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 29:1-29:30, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{saks_et_al:LIPIcs.CCC.2022.29,
  author =	{Saks, Michael and Santhanam, Rahul},
  title =	{{On Randomized Reductions to the Random Strings}},
  booktitle =	{37th Computational Complexity Conference (CCC 2022)},
  pages =	{29:1--29:30},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-241-9},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{234},
  editor =	{Lovett, Shachar},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2022.29},
  URN =		{urn:nbn:de:0030-drops-165912},
  doi =		{10.4230/LIPIcs.CCC.2022.29},
  annote =	{Keywords: Kolmogorov complexity, randomized reductions}
}
Document
Average-Case Hardness of NP and PH from Worst-Case Fine-Grained Assumptions

Authors: Lijie Chen, Shuichi Hirahara, and Neekon Vafa

Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)


Abstract
What is a minimal worst-case complexity assumption that implies non-trivial average-case hardness of NP or PH? This question is well motivated by the theory of fine-grained average-case complexity and fine-grained cryptography. In this paper, we show that several standard worst-case complexity assumptions are sufficient to imply non-trivial average-case hardness of NP or PH: - NTIME[n] cannot be solved in quasi-linear time on average if UP ̸ ⊆ DTIME[2^{Õ(√n)}]. - Σ₂TIME[n] cannot be solved in quasi-linear time on average if Σ_kSAT cannot be solved in time 2^{Õ(√n)} for some constant k. Previously, it was not known if even average-case hardness of Σ₃SAT implies the average-case hardness of Σ₂TIME[n]. - Under the Exponential-Time Hypothesis (ETH), there is no average-case n^{1+ε}-time algorithm for NTIME[n] whose running time can be estimated in time n^{1+ε} for some constant ε > 0. Our results are given by generalizing the non-black-box worst-case-to-average-case connections presented by Hirahara (STOC 2021) to the settings of fine-grained complexity. To do so, we construct quite efficient complexity-theoretic pseudorandom generators under the assumption that the nondeterministic linear time is easy on average, which may be of independent interest.

Cite as

Lijie Chen, Shuichi Hirahara, and Neekon Vafa. Average-Case Hardness of NP and PH from Worst-Case Fine-Grained Assumptions. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 45:1-45:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.ITCS.2022.45,
  author =	{Chen, Lijie and Hirahara, Shuichi and Vafa, Neekon},
  title =	{{Average-Case Hardness of NP and PH from Worst-Case Fine-Grained Assumptions}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{45:1--45:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.45},
  URN =		{urn:nbn:de:0030-drops-156411},
  doi =		{10.4230/LIPIcs.ITCS.2022.45},
  annote =	{Keywords: Average-case complexity, worst-case to average-case reduction}
}
Document
Errorless Versus Error-Prone Average-Case Complexity

Authors: Shuichi Hirahara and Rahul Santhanam

Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)


Abstract
We consider the question of whether errorless and error-prone notions of average-case hardness are equivalent, and make several contributions. First, we study this question in the context of hardness for NP, and connect it to the long-standing open question of whether there are instance checkers for NP. We show that there is an efficient non-uniform non-adaptive reduction from errorless to error-prone heuristics for NP if and only if there is an efficient non-uniform average-case non-adaptive instance-checker for NP. We also suggest an approach to proving equivalence of the two notions of average-case hardness for PH. Second, we show unconditionally that error-prone average-case hardness is equivalent to errorless average-case hardness for P against NC¹ and for UP ∩ coUP against P. Third, we apply our results about errorless and error-prone average-case hardness to get new equivalences between hitting set generators and pseudo-random generators.

Cite as

Shuichi Hirahara and Rahul Santhanam. Errorless Versus Error-Prone Average-Case Complexity. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 84:1-84:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{hirahara_et_al:LIPIcs.ITCS.2022.84,
  author =	{Hirahara, Shuichi and Santhanam, Rahul},
  title =	{{Errorless Versus Error-Prone Average-Case Complexity}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{84:1--84:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.84},
  URN =		{urn:nbn:de:0030-drops-156803},
  doi =		{10.4230/LIPIcs.ITCS.2022.84},
  annote =	{Keywords: average-case complexity, instance checker, pseudorandomness}
}
Document
Excluding PH Pessiland

Authors: Shuichi Hirahara and Rahul Santhanam

Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)


Abstract
Heuristica and Pessiland are "worlds" of average-case complexity [Impagliazzo95] that are considered unlikely but that current techniques are unable to rule out. Recently, [Hirahara20] considered a PH (Polynomial Hierarchy) analogue of Heuristica, and showed that to rule it out, it would be sufficient to prove the NP-completeness of the problem GapMINKT^PH of estimating the PH-oracle time-bounded Kolmogorov complexity of a string. In this work, we analogously define "PH Pessiland" to be a world where PH is hard on average but PH-computable pseudo-random generators do not exist. We unconditionally rule out PH-Pessiland in both non-uniform and uniform settings, by showing that the distributional problem of computing PH-oracle time-bounded Kolmogorov complexity of a string over the uniform distribution is complete for an (error-prone) average-case analogue of PH. Moreover, we show the equivalence between error-prone average-case hardness of PH and the existence of PH-computable pseudorandom generators.

Cite as

Shuichi Hirahara and Rahul Santhanam. Excluding PH Pessiland. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 85:1-85:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{hirahara_et_al:LIPIcs.ITCS.2022.85,
  author =	{Hirahara, Shuichi and Santhanam, Rahul},
  title =	{{Excluding PH Pessiland}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{85:1--85:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.85},
  URN =		{urn:nbn:de:0030-drops-156819},
  doi =		{10.4230/LIPIcs.ITCS.2022.85},
  annote =	{Keywords: average-case complexity, pseudorandomness, meta-complexity}
}
Document
Cryptographic Hardness Under Projections for Time-Bounded Kolmogorov Complexity

Authors: Eric Allender, John Gouwar, Shuichi Hirahara, and Caleb Robelle

Published in: LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)


Abstract
A version of time-bounded Kolmogorov complexity, denoted KT, has received attention in the past several years, due to its close connection to circuit complexity and to the Minimum Circuit Size Problem MCSP. Essentially all results about the complexity of MCSP hold also for MKTP (the problem of computing the KT complexity of a string). Both MKTP and MCSP are hard for SZK (Statistical Zero Knowledge) under BPP-Turing reductions; neither is known to be NP-complete. Recently, some hardness results for MKTP were proved that are not (yet) known to hold for MCSP. In particular, MKTP is hard for DET (a subclass of P) under nonuniform ≤^{NC^0}_m reductions. In this paper, we improve this, to show that the complement of MKTP is hard for the (apparently larger) class NISZK_L under not only ≤^{NC^0}_m reductions but even under projections. Also, the complement of MKTP is hard for NISZK under ≤^{P/poly}_m reductions. Here, NISZK is the class of problems with non-interactive zero-knowledge proofs, and NISZK_L is the non-interactive version of the class SZK_L that was studied by Dvir et al. As an application, we provide several improved worst-case to average-case reductions to problems in NP, and we obtain a new lower bound on MKTP (which is currently not known to hold for MCSP).

Cite as

Eric Allender, John Gouwar, Shuichi Hirahara, and Caleb Robelle. Cryptographic Hardness Under Projections for Time-Bounded Kolmogorov Complexity. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 54:1-54:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{allender_et_al:LIPIcs.ISAAC.2021.54,
  author =	{Allender, Eric and Gouwar, John and Hirahara, Shuichi and Robelle, Caleb},
  title =	{{Cryptographic Hardness Under Projections for Time-Bounded Kolmogorov Complexity}},
  booktitle =	{32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
  pages =	{54:1--54:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-214-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{212},
  editor =	{Ahn, Hee-Kap and Sadakane, Kunihiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.54},
  URN =		{urn:nbn:de:0030-drops-154875},
  doi =		{10.4230/LIPIcs.ISAAC.2021.54},
  annote =	{Keywords: Kolmogorov Complexity, Interactive Proofs, Minimum Circuit Size Problem, Worst-case to Average-case Reductions}
}
Document
Test of Quantumness with Small-Depth Quantum Circuits

Authors: Shuichi Hirahara and François Le Gall

Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)


Abstract
Recently Brakerski, Christiano, Mahadev, Vazirani and Vidick (FOCS 2018) have shown how to construct a test of quantumness based on the learning with errors (LWE) assumption: a test that can be solved efficiently by a quantum computer but cannot be solved by a classical polynomial-time computer under the LWE assumption. This test has lead to several cryptographic applications. In particular, it has been applied to producing certifiable randomness from a single untrusted quantum device, self-testing a single quantum device and device-independent quantum key distribution. In this paper, we show that this test of quantumness, and essentially all the above applications, can actually be implemented by a very weak class of quantum circuits: constant-depth quantum circuits combined with logarithmic-depth classical computation. This reveals novel complexity-theoretic properties of this fundamental test of quantumness and gives new concrete evidence of the superiority of small-depth quantum circuits over classical computation.

Cite as

Shuichi Hirahara and François Le Gall. Test of Quantumness with Small-Depth Quantum Circuits. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 59:1-59:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{hirahara_et_al:LIPIcs.MFCS.2021.59,
  author =	{Hirahara, Shuichi and Le Gall, Fran\c{c}ois},
  title =	{{Test of Quantumness with Small-Depth Quantum Circuits}},
  booktitle =	{46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)},
  pages =	{59:1--59:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-201-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{202},
  editor =	{Bonchi, Filippo and Puglisi, Simon J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.59},
  URN =		{urn:nbn:de:0030-drops-144996},
  doi =		{10.4230/LIPIcs.MFCS.2021.59},
  annote =	{Keywords: Quantum computing, small-depth circuits, quantum cryptography}
}
  • Refine by Author
  • 22 Hirahara, Shuichi
  • 7 Santhanam, Rahul
  • 3 Allender, Eric
  • 3 Kabanets, Valentine
  • 3 Oliveira, Igor C.
  • Show More...

  • Refine by Classification
  • 9 Theory of computation → Complexity classes
  • 8 Theory of computation → Computational complexity and cryptography
  • 7 Theory of computation → Problems, reductions and completeness
  • 6 Theory of computation → Pseudorandomness and derandomization
  • 5 Theory of computation → Circuit complexity
  • Show More...

  • Refine by Keyword
  • 9 average-case complexity
  • 6 Minimum Circuit Size Problem
  • 5 Kolmogorov complexity
  • 5 meta-complexity
  • 3 Kolmogorov Complexity
  • Show More...

  • Refine by Type
  • 30 document

  • Refine by Publication Year
  • 7 2022
  • 6 2020
  • 5 2023
  • 4 2021
  • 2 2017
  • Show More...

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail