4 Search Results for "Chapman, Brynmor"

Document
DOI: 10.4230/LIPIcs.ITCS.2023.99
On Oracles and Algorithmic Methods for Proving Lower Bounds

Authors: Nikhil Vyas and Ryan Williams

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

Abstract
This paper studies the interaction of oracles with algorithmic approaches to proving circuit complexity lower bounds, establishing new results on two different kinds of questions. 1) We revisit some prominent open questions in circuit lower bounds, and provide a clean way of viewing them as circuit upper bound questions. Let Missing-String be the (total) search problem of producing a string that does not appear in a given list L containing M bit-strings of length N, where M < 2ⁿ. We show in a generic way how algorithms and uniform circuits (from restricted classes) for Missing-String imply complexity lower bounds (and in some cases, the converse holds as well). We give a local algorithm for Missing-String, which can compute any desired output bit making very few probes into the input, when the number of strings M is small enough. We apply this to prove a new nearly-optimal (up to oracles) time hierarchy theorem with advice. We show that the problem of constructing restricted uniform circuits for Missing-String is essentially equivalent to constructing functions without small non-uniform circuits, in a relativizing way. For example, we prove that small uniform depth-3 circuits for Missing-String would imply exponential circuit lower bounds for Σ₂ EXP, and depth-3 lower bounds for Missing-String would imply non-trivial circuits (relative to an oracle) for Σ₂ EXP problems. Both conclusions are longstanding open problems in circuit complexity. 2) It has been known since Impagliazzo, Kabanets, and Wigderson [JCSS 2002] that generic derandomizations improving subexponentially over exhaustive search would imply lower bounds such as NEXP ̸ ⊂ 𝖯/poly. Williams [SICOMP 2013] showed that Circuit-SAT algorithms running barely faster than exhaustive search would imply similar lower bounds. The known proofs of such results do not relativize (they use techniques from interactive proofs/PCPs). However, it has remained open whether there is an oracle under which the generic implications from circuit-analysis algorithms to circuit lower bounds fail. Building on an oracle of Fortnow, we construct an oracle relative to which the circuit approximation probability problem (CAPP) is in 𝖯, yet EXP^{NP} has polynomial-size circuits. We construct an oracle relative to which SAT can be solved in "half-exponential" time, yet exponential time (EXP) has polynomial-size circuits. Improving EXP to NEXP would give an oracle relative to which Σ₂ 𝖤 has "half-exponential" size circuits, which is open. (Recall it is known that Σ₂ 𝖤 is not in "sub-half-exponential" size, and the proof relativizes.) Moreover, the running time of the SAT algorithm cannot be improved: relative to all oracles, if SAT is in "sub-half-exponential" time then EXP does not have polynomial-size circuits.
Cite as

Nikhil Vyas and Ryan Williams. On Oracles and Algorithmic Methods for Proving Lower Bounds. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 99:1-99:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{vyas_et_al:LIPIcs.ITCS.2023.99,
  author =	{Vyas, Nikhil and Williams, Ryan},
  title =	{{On Oracles and Algorithmic Methods for Proving Lower Bounds}},
  booktitle =	{14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
  pages =	{99:1--99:26},
  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.99},
  URN =		{urn:nbn:de:0030-drops-176021},
  doi =		{10.4230/LIPIcs.ITCS.2023.99},
  annote =	{Keywords: oracles, relativization, circuit complexity, missing string, exponential hierarchy}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2022.38
Smaller ACC0 Circuits for Symmetric Functions

Authors: Brynmor Chapman and R. Ryan Williams

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

Abstract
What is the power of constant-depth circuits with MOD_m gates, that can count modulo m? Can they efficiently compute MAJORITY and other symmetric functions? When m is a constant prime power, the answer is well understood. In this regime, Razborov and Smolensky proved in the 1980s that MAJORITY and MOD_m require super-polynomial-size MOD_q circuits, where q is any prime power not dividing m. However, relatively little is known about the power of MOD_m gates when m is not a prime power. For example, it is still open whether every problem decidable in exponential time can be computed by depth-3 circuits of polynomial-size and only MOD_6 gates. In this paper, we shed some light on the difficulty of proving lower bounds for MOD_m circuits, by giving new upper bounds. We show how to construct MOD_m circuits computing symmetric functions with non-prime power m, with size-depth tradeoffs that beat the longstanding lower bounds for AC^0[m] circuits when m is a prime power. Furthermore, we observe that our size-depth tradeoff circuits have essentially optimal dependence on m and d in the exponent, under a natural circuit complexity hypothesis. For example, we show that for every ε > 0, every symmetric function can be computed using MOD_m circuits of depth 3 and 2^{n^ε} size, for a constant m depending only on ε > 0. In other words, depth-3 CC^0 circuits can compute any symmetric function in subexponential size. This demonstrates a significant difference in the power of depth-3 CC^0 circuits, compared to other models: for certain symmetric functions, depth-3 AC^0 circuits require 2^{Ω(√n)} size [Håstad 1986], and depth-3 AC^0[p^k] circuits (for fixed prime power p^k) require 2^{Ω(n^{1/6})} size [Smolensky 1987]. Even for depth-2 MOD_p ∘ MOD_m circuits, 2^{Ω(n)} lower bounds were known [Barrington Straubing Thérien 1990].
Cite as

Brynmor Chapman and R. Ryan Williams. Smaller ACC0 Circuits for Symmetric Functions. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 38:1-38:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{chapman_et_al:LIPIcs.ITCS.2022.38,
  author =	{Chapman, Brynmor and Williams, R. Ryan},
  title =	{{Smaller ACC0 Circuits for Symmetric Functions}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{38:1--38:19},
  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.38},
  URN =		{urn:nbn:de:0030-drops-156342},
  doi =		{10.4230/LIPIcs.ITCS.2022.38},
  annote =	{Keywords: ACC, CC, circuit complexity, symmetric functions, Chinese Remainder Theorem}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2021.29
Black-Box Hypotheses and Lower Bounds

Authors: Brynmor K. Chapman and R. Ryan Williams

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

Abstract
What sort of code is so difficult to analyze that every potential analyst can discern essentially no information from the code, other than its input-output behavior? In their seminal work on program obfuscation, Barak, Goldreich, Impagliazzo, Rudich, Sahai, Vadhan, and Yang (CRYPTO 2001) proposed the Black-Box Hypothesis, which roughly states that every property of Boolean functions which has an efficient "analyst" and is "code independent" can also be computed by an analyst that only has black-box access to the code. In their formulation of the Black-Box Hypothesis, the "analysts" are arbitrary randomized polynomial-time algorithms, and the "codes" are general (polynomial-size) circuits. If true, the Black-Box Hypothesis would immediately imply NP ̸ ⊂ BPP. We consider generalized forms of the Black-Box Hypothesis, where the set of "codes" 𝒞 and the set of "analysts" 𝒜 may correspond to other efficient models of computation, from more restricted models such as AC⁰ to more general models such as nondeterministic circuits. We show how lower bounds of the form 𝒞 ̸ ⊂ 𝒜 often imply a corresponding Black-Box Hypothesis for those respective codes and analysts. We investigate the possibility of "complete" problems for the Black-Box Hypothesis: problems in 𝒞 such that they are not in 𝒜 if and only if their corresponding Black-Box Hypothesis is true. Along the way, we prove an equivalence: for nondeterministic circuit classes 𝒞, the "𝒞-circuit satisfiability problem" is not in 𝒜 if and only if the Black-Box Hypothesis is true for analysts in 𝒜.
Cite as

Brynmor K. Chapman and R. Ryan Williams. Black-Box Hypotheses and Lower Bounds. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 29:1-29:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{chapman_et_al:LIPIcs.MFCS.2021.29,
  author =	{Chapman, Brynmor K. and Williams, R. Ryan},
  title =	{{Black-Box Hypotheses and Lower Bounds}},
  booktitle =	{46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)},
  pages =	{29:1--29:22},
  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.29},
  URN =		{urn:nbn:de:0030-drops-144698},
  doi =		{10.4230/LIPIcs.MFCS.2021.29},
  annote =	{Keywords: Black-Box hypothesis, circuit complexity, lower bounds}
}
Document
DOI: 10.4230/LIPIcs.CONCUR.2018.42
Effective Divergence Analysis for Linear Recurrence Sequences

Authors: Shaull Almagor, Brynmor Chapman, Mehran Hosseini, Joël Ouaknine, and James Worrell

Published in: LIPIcs, Volume 118, 29th International Conference on Concurrency Theory (CONCUR 2018)

Abstract
We study the growth behaviour of rational linear recurrence sequences. We show that for low-order sequences, divergence is decidable in polynomial time. We also exhibit a polynomial-time algorithm which takes as input a divergent rational linear recurrence sequence and computes effective fine-grained lower bounds on the growth rate of the sequence.
Cite as

Shaull Almagor, Brynmor Chapman, Mehran Hosseini, Joël Ouaknine, and James Worrell. Effective Divergence Analysis for Linear Recurrence Sequences. In 29th International Conference on Concurrency Theory (CONCUR 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 118, pp. 42:1-42:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{almagor_et_al:LIPIcs.CONCUR.2018.42,
  author =	{Almagor, Shaull and Chapman, Brynmor and Hosseini, Mehran and Ouaknine, Jo\"{e}l and Worrell, James},
  title =	{{Effective Divergence Analysis for Linear Recurrence Sequences}},
  booktitle =	{29th International Conference on Concurrency Theory (CONCUR 2018)},
  pages =	{42:1--42:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-087-3},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{118},
  editor =	{Schewe, Sven and Zhang, Lijun},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2018.42},
  URN =		{urn:nbn:de:0030-drops-95802},
  doi =		{10.4230/LIPIcs.CONCUR.2018.42},
  annote =	{Keywords: Linear recurrence sequences, Divergence, Algebraic numbers, Positivity}
}
  • Refine by Author
  • 2 Chapman, Brynmor
  • 2 Williams, R. Ryan
  • 1 Almagor, Shaull
  • 1 Chapman, Brynmor K.
  • 1 Hosseini, Mehran
  • Show More...

  • Refine by Classification
  • 3 Theory of computation → Circuit complexity
  • 1 Computing methodologies → Algebraic algorithms
  • 1 Theory of computation → Complexity classes
  • 1 Theory of computation → Logic and verification

  • Refine by Keyword
  • 3 circuit complexity
  • 1 ACC
  • 1 Algebraic numbers
  • 1 Black-Box hypothesis
  • 1 CC
  • Show More...

  • Refine by Type
  • 4 document

  • Refine by Publication Year
  • 1 2018
  • 1 2021
  • 1 2022
  • 1 2023

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 Imprint Privacy Contact