DROPS

Document

DOI: 10.4230/LIPIcs.ITCS.2023.35

Black-Box Constructive Proofs Are Unavoidable

Authors: Lijie Chen, Ryan Williams, and Tianqi Yang

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

Abstract

Following Razborov and Rudich, a "natural property" for proving a circuit lower bound satisfies three axioms: constructivity, largeness, and usefulness. In 2013, Williams proved that for any reasonable circuit class C, NEXP ⊂ C is equivalent to the existence of a constructive property useful against C. Here, a property is constructive if it can be decided in poly(N) time, where N = 2ⁿ is the length of the truth-table of the given n-input function. Recently, Fan, Li, and Yang initiated the study of black-box natural properties, which require a much stronger notion of constructivity, called black-box constructivity: the property should be decidable in randomized polylog(N) time, given oracle access to the n-input function. They showed that most proofs based on random restrictions yield black-box natural properties, and demonstrated limitations on what black-box natural properties can prove. In this paper, perhaps surprisingly, we prove that the equivalence of Williams holds even with this stronger notion of black-box constructivity: for any reasonable circuit class C, NEXP ⊂ C is equivalent to the existence of a black-box constructive property useful against C. The main technical ingredient in proving this equivalence is a smooth, strong, and locally-decodable probabilistically checkable proof (PCP), which we construct based on a recent work by Paradise. As a by-product, we show that average-case witness lower bounds for PCP verifiers follow from NEXP lower bounds. We also show that randomness is essential in the definition of black-box constructivity: we unconditionally prove that there is no deterministic polylog(N)-time constructive property that is useful against even polynomial-size AC⁰ circuits.

Cite as

Lijie Chen, Ryan Williams, and Tianqi Yang. Black-Box Constructive Proofs Are Unavoidable. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 35:1-35:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.ITCS.2023.35,
  author =	{Chen, Lijie and Williams, Ryan and Yang, Tianqi},
  title =	{{Black-Box Constructive Proofs Are Unavoidable}},
  booktitle =	{14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
  pages =	{35:1--35:24},
  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.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.35},
  URN =		{urn:nbn:de:0030-drops-175380},
  doi =		{10.4230/LIPIcs.ITCS.2023.35},
  annote =	{Keywords: Circuit lower bounds, natural proofs, probabilistic checkable proofs}
}

Document

DOI: 10.4230/LIPIcs.CCC.2022.23

Extremely Efficient Constructions of Hash Functions, with Applications to Hardness Magnification and PRFs

Authors: Lijie Chen, Jiatu Li, and Tianqi Yang

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

Abstract

In a recent work, Fan, Li, and Yang (STOC 2022) constructed a family of almost-universal hash functions such that each function in the family is computable by (2n + o(n))-gate circuits of fan-in 2 over the B₂ basis. Applying this family, they established the existence of pseudorandom functions computable by circuits of the same complexity, under the standard assumption that OWFs exist. However, a major disadvantage of the hash family construction by Fan, Li, and Yang (STOC 2022) is that it requires a seed length of poly(n), which limits its potential applications. We address this issue by giving an improved construction of almost-universal hash functions with seed length polylog(n), such that each function in the family is computable with POLYLOGTIME-uniform (2n + o(n))-gate circuits. Our new construction has the following applications in both complexity theory and cryptography. - (Hardness magnification). Let α : ℕ → ℕ be any function such that α(n) ≤ log n / log log n. We show that if there is an n^{α(n)}-sparse NP language that does not have probabilistic circuits of 2n + O(n/log log n) gates, then we have (1) NTIME[2ⁿ] ⊈ SIZE[2^{n^{1/5}}] and (2) NP ⊈ SIZE[n^k] for every constant k. Complementing this magnification phenomenon, we present an O(n)-sparse language in P which requires probabilistic circuits of size at least 2n - 2. This is the first result in hardness magnification showing that even a sub-linear additive improvement on known circuit size lower bounds would imply NEXP ⊄ P_{/poly}. Following Chen, Jin, and Williams (STOC 2020), we also establish a sharp threshold for explicit obstructions: we give an explict obstruction against (2n-2)-size circuits, and prove that a sub-linear additive improvement on the circuit size would imply (1) DTIME[2ⁿ] ⊈ SIZE[2^{n^{1/5}}] and (2) P ⊈ SIZE[n^k] for every constant k. - (Extremely efficient construction of pseudorandom functions). Assuming that one of integer factoring, decisional Diffie-Hellman, or ring learning-with-errors is sub-exponentially hard, we show the existence of pseudorandom functions computable by POLYLOGTIME-uniform AC⁰[2] circuits with 2n + o(n) wires, with key length polylog(n). We also show that PRFs computable by POLYLOGTIME-uniform B₂ circuits of 2n + o(n) gates follows from the existence of sub-exponentially secure one-way functions.

Cite as

Lijie Chen, Jiatu Li, and Tianqi Yang. Extremely Efficient Constructions of Hash Functions, with Applications to Hardness Magnification and PRFs. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 23:1-23:37, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.CCC.2022.23,
  author =	{Chen, Lijie and Li, Jiatu and Yang, Tianqi},
  title =	{{Extremely Efficient Constructions of Hash Functions, with Applications to Hardness Magnification and PRFs}},
  booktitle =	{37th Computational Complexity Conference (CCC 2022)},
  pages =	{23:1--23:37},
  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.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2022.23},
  URN =		{urn:nbn:de:0030-drops-165852},
  doi =		{10.4230/LIPIcs.CCC.2022.23},
  annote =	{Keywords: Almost universal hash functions, hardness magnification, pseudorandom functions}
}

Document

DOI: 10.4230/LIPIcs.SoCG.2020.36

An Efficient Algorithm for 1-Dimensional (Persistent) Path Homology

Authors: Tamal K. Dey, Tianqi Li, and Yusu Wang

Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)

Abstract

This paper focuses on developing an efficient algorithm for analyzing a directed network (graph) from a topological viewpoint. A prevalent technique for such topological analysis involves computation of homology groups and their persistence. These concepts are well suited for spaces that are not directed. As a result, one needs a concept of homology that accommodates orientations in input space. Path-homology developed for directed graphs by Grigoryan, Lin, Muranov and Yau has been effectively adapted for this purpose recently by Chowdhury and Mémoli. They also give an algorithm to compute this path-homology. Our main contribution in this paper is an algorithm that computes this path-homology and its persistence more efficiently for the 1-dimensional (H₁) case. In developing such an algorithm, we discover various structures and their efficient computations that aid computing the 1-dimensional path-homology. We implement our algorithm and present some preliminary experimental results.

Cite as

Tamal K. Dey, Tianqi Li, and Yusu Wang. An Efficient Algorithm for 1-Dimensional (Persistent) Path Homology. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 36:1-36:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{dey_et_al:LIPIcs.SoCG.2020.36,
  author =	{Dey, Tamal K. and Li, Tianqi and Wang, Yusu},
  title =	{{An Efficient Algorithm for 1-Dimensional (Persistent) Path Homology}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{36:1--36:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-143-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{164},
  editor =	{Cabello, Sergio and Chen, Danny Z.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.36},
  URN =		{urn:nbn:de:0030-drops-121944},
  doi =		{10.4230/LIPIcs.SoCG.2020.36},
  annote =	{Keywords: computational topology, directed graph, path homology, persistent path homology}
}

3 Search Results for "Li, Tianqi"

Black-Box Constructive Proofs Are Unavoidable

Abstract

Cite as

Extremely Efficient Constructions of Hash Functions, with Applications to Hardness Magnification and PRFs

Abstract

Cite as

An Efficient Algorithm for 1-Dimensional (Persistent) Path Homology

Abstract

Cite as

Thanks for your feedback!

Could not send message