Search Results

Documents authored by Ren, Hanlin

Document
DOI: 10.4230/LIPIcs.CCC.2023.6
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.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
DOI: 10.4230/LIPIcs.STACS.2022.54
A Relativization Perspective on Meta-Complexity

Authors: Hanlin Ren and Rahul Santhanam

Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)

Abstract
Meta-complexity studies the complexity of computational problems about complexity theory, such as the Minimum Circuit Size Problem (MCSP) and its variants. We show that a relativization barrier applies to many important open questions in meta-complexity. We give relativized worlds where: 1) MCSP can be solved in deterministic polynomial time, but the search version of MCSP cannot be solved in deterministic polynomial time, even approximately. In contrast, Carmosino, Impagliazzo, Kabanets, Kolokolova [CCC'16] gave a randomized approximate search-to-decision reduction for MCSP with a relativizing proof. 2) The complexities of MCSP[2^{n/2}] and MCSP[2^{n/4}] are different, in both worst-case and average-case settings. Thus the complexity of MCSP is not "robust" to the choice of the size function. 3) Levin’s time-bounded Kolmogorov complexity Kt(x) can be approximated to a factor (2+ε) in polynomial time, for any ε > 0. 4) Natural proofs do not exist, and neither do auxiliary-input one-way functions. In contrast, Santhanam [ITCS'20] gave a relativizing proof that the non-existence of natural proofs implies the existence of one-way functions under a conjecture about optimal hitting sets. 5) DistNP does not reduce to GapMINKT by a family of "robust" reductions. This presents a technical barrier for solving a question of Hirahara [FOCS'20].
Cite as

Hanlin Ren and Rahul Santhanam. A Relativization Perspective on Meta-Complexity. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 54:1-54:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{ren_et_al:LIPIcs.STACS.2022.54,
  author =	{Ren, Hanlin and Santhanam, Rahul},
  title =	{{A Relativization Perspective on Meta-Complexity}},
  booktitle =	{39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)},
  pages =	{54:1--54:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-222-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{219},
  editor =	{Berenbrink, Petra and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2022.54},
  URN =		{urn:nbn:de:0030-drops-158646},
  doi =		{10.4230/LIPIcs.STACS.2022.54},
  annote =	{Keywords: meta-complexity, relativization, minimum circuit size problem}
}
Document
DOI: 10.4230/LIPIcs.CCC.2021.35
Hardness of KT Characterizes Parallel Cryptography

Authors: Hanlin Ren and Rahul Santhanam

Published in: LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021)

Abstract
A recent breakthrough of Liu and Pass (FOCS'20) shows that one-way functions exist if and only if the (polynomial-)time-bounded Kolmogorov complexity, K^t, is bounded-error hard on average to compute. In this paper, we strengthen this result and extend it to other complexity measures: - We show, perhaps surprisingly, that the KT complexity is bounded-error average-case hard if and only if there exist one-way functions in constant parallel time (i.e. NC⁰). This result crucially relies on the idea of randomized encodings. Previously, a seminal work of Applebaum, Ishai, and Kushilevitz (FOCS'04; SICOMP'06) used the same idea to show that NC⁰-computable one-way functions exist if and only if logspace-computable one-way functions exist. - Inspired by the above result, we present randomized average-case reductions among the NC¹-versions and logspace-versions of K^t complexity, and the KT complexity. Our reductions preserve both bounded-error average-case hardness and zero-error average-case hardness. To the best of our knowledge, this is the first reduction between the KT complexity and a variant of K^t complexity. - We prove tight connections between the hardness of K^t complexity and the hardness of (the hardest) one-way functions. In analogy with the Exponential-Time Hypothesis and its variants, we define and motivate the Perebor Hypotheses for complexity measures such as K^t and KT. We show that a Strong Perebor Hypothesis for K^t implies the existence of (weak) one-way functions of near-optimal hardness 2^{n-o(n)}. To the best of our knowledge, this is the first construction of one-way functions of near-optimal hardness based on a natural complexity assumption about a search problem. - We show that a Weak Perebor Hypothesis for MCSP implies the existence of one-way functions, and establish a partial converse. This is the first unconditional construction of one-way functions from the hardness of MCSP over a natural distribution. - Finally, we study the average-case hardness of MKtP. We show that it characterizes cryptographic pseudorandomness in one natural regime of parameters, and complexity-theoretic pseudorandomness in another natural regime.
Cite as

Hanlin Ren and Rahul Santhanam. Hardness of KT Characterizes Parallel Cryptography. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 35:1-35:58, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{ren_et_al:LIPIcs.CCC.2021.35,
  author =	{Ren, Hanlin and Santhanam, Rahul},
  title =	{{Hardness of KT Characterizes Parallel Cryptography}},
  booktitle =	{36th Computational Complexity Conference (CCC 2021)},
  pages =	{35:1--35:58},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-193-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{200},
  editor =	{Kabanets, Valentine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021.35},
  URN =		{urn:nbn:de:0030-drops-143091},
  doi =		{10.4230/LIPIcs.CCC.2021.35},
  annote =	{Keywords: one-way function, meta-complexity, KT complexity, parallel cryptography, randomized encodings}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2021.76
Constructing a Distance Sensitivity Oracle in O(n^2.5794 M) Time

Authors: Yong Gu and Hanlin Ren

Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)

Abstract
We continue the study of distance sensitivity oracles (DSOs). Given a directed graph G with n vertices and edge weights in {1, 2, … , M}, we want to build a data structure such that given any source vertex u, any target vertex v, and any failure f (which is either a vertex or an edge), it outputs the length of the shortest path from u to v not going through f. Our main result is a DSO with preprocessing time O(n^2.5794 M) and constant query time. Previously, the best preprocessing time of DSOs for directed graphs is O(n^2.7233 M), and even in the easier case of undirected graphs, the best preprocessing time is O(n^2.6865 M) [Ren, ESA 2020]. One drawback of our DSOs, though, is that it only supports distance queries but not path queries. Our main technical ingredient is an algorithm that computes the inverse of a degree-d polynomial matrix (i.e. a matrix whose entries are degree-d univariate polynomials) modulo x^r. The algorithm is adapted from [Zhou, Labahn and Storjohann, Journal of Complexity, 2015], and we replace some of its intermediate steps with faster rectangular matrix multiplication algorithms. We also show how to compute unique shortest paths in a directed graph with edge weights in {1, 2, … , M}, in O(n^2.5286 M) time. This algorithm is crucial in the preprocessing algorithm of our DSO. Our solution improves the O(n^2.6865 M) time bound in [Ren, ESA 2020], and matches the current best time bound for computing all-pairs shortest paths.
Cite as

Yong Gu and Hanlin Ren. Constructing a Distance Sensitivity Oracle in O(n^2.5794 M) Time. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 76:1-76:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{gu_et_al:LIPIcs.ICALP.2021.76,
  author =	{Gu, Yong and Ren, Hanlin},
  title =	{{Constructing a Distance Sensitivity Oracle in O(n^2.5794 M) Time}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{76:1--76:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.76},
  URN =		{urn:nbn:de:0030-drops-141450},
  doi =		{10.4230/LIPIcs.ICALP.2021.76},
  annote =	{Keywords: graph theory, shortest paths, distance sensitivity oracles}
}
Document
DOI: 10.4230/LIPIcs.ESA.2020.79
Improved Distance Sensitivity Oracles with Subcubic Preprocessing Time

Authors: Hanlin Ren

Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)

Abstract
We consider the problem of building Distance Sensitivity Oracles (DSOs). Given a directed graph G = (V, E) with edge weights in {1, 2, … , M}, we need to preprocess it into a data structure, and answer the following queries: given vertices u,v,x ∈ V, output the length of the shortest path from u to v that does not go through x. Our main result is a simple DSO with Õ(n^2.7233 M²) preprocessing time and O(1) query time. Moreover, if the input graph is undirected, the preprocessing time can be improved to Õ(n^2.6865 M²). Our algorithms are randomized with correct probability ≥ 1-1/n^c, for a constant c that can be made arbitrarily large. Previously, there is a DSO with Õ(n^2.8729 M) preprocessing time and polylog(n) query time [Chechik and Cohen, STOC'20]. At the core of our DSO is the following observation from [Bernstein and Karger, STOC'09]: if there is a DSO with preprocessing time P and query time Q, then we can construct a DSO with preprocessing time P+Õ(Mn²)⋅ Q and query time O(1). (Here Õ(⋅) hides polylog(n) factors.)
Cite as

Hanlin Ren. Improved Distance Sensitivity Oracles with Subcubic Preprocessing Time. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 79:1-79:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{ren:LIPIcs.ESA.2020.79,
  author =	{Ren, Hanlin},
  title =	{{Improved Distance Sensitivity Oracles with Subcubic Preprocessing Time}},
  booktitle =	{28th Annual European Symposium on Algorithms (ESA 2020)},
  pages =	{79:1--79:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-162-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{173},
  editor =	{Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.79},
  URN =		{urn:nbn:de:0030-drops-129450},
  doi =		{10.4230/LIPIcs.ESA.2020.79},
  annote =	{Keywords: Graph theory, Failure-prone structures}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2018.42
Approximating All-Pair Bounded-Leg Shortest Path and APSP-AF in Truly-Subcubic Time

Authors: Ran Duan and Hanlin Ren

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Abstract
In the bounded-leg shortest path (BLSP) problem, we are given a weighted graph G with nonnegative edge lengths, and we want to answer queries of the form "what's the shortest path from u to v, where only edges of length <=L are considered?". A more general problem is the APSP-AF (all-pair shortest path for all flows) problem, in which each edge has two weights - a length d and a capacity f, and a query asks about the shortest path from u to v where only edges of capacity >= f are considered. In this article we give an O~(n^{(omega+3)/2}epsilon^{-3/2}log W) time algorithm to compute a data structure that answers APSP-AF queries in O(log(epsilon^{-1}log (nW))) time and achieves (1+epsilon)-approximation, where omega < 2.373 is the exponent of time complexity of matrix multiplication, W is the upper bound of integer edge lengths, and n is the number of vertices. This is the first truly-subcubic time algorithm for these problems on dense graphs. Our algorithm utilizes the O(n^{(omega+3)/2}) time max-min product algorithm [Duan and Pettie 2009]. Since the all-pair bottleneck path (APBP) problem, which is equivalent to max-min product, can be seen as all-pair reachability for all flow, our approach indeed shows that these problems are almost equivalent in the approximation sense.
Cite as

Ran Duan and Hanlin Ren. Approximating All-Pair Bounded-Leg Shortest Path and APSP-AF in Truly-Subcubic Time. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 42:1-42:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{duan_et_al:LIPIcs.ICALP.2018.42,
  author =	{Duan, Ran and Ren, Hanlin},
  title =	{{Approximating All-Pair Bounded-Leg Shortest Path and APSP-AF in Truly-Subcubic Time}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{42:1--42:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.42},
  URN =		{urn:nbn:de:0030-drops-90467},
  doi =		{10.4230/LIPIcs.ICALP.2018.42},
  annote =	{Keywords: Graph Theory, Approximation Algorithms, Combinatorial Optimization}
}
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
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact