2 Search Results for "Castrill�n-Mazo, Jer�nimo"

Document
DOI: 10.4230/LIPIcs.CCC.2022.17
Nisan-Wigderson Generators in Proof Complexity: New Lower Bounds

Authors: Erfan Khaniki

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

Abstract
A map g:{0,1}ⁿ → {0,1}^m (m > n) is a hard proof complexity generator for a proof system P iff for every string b ∈ {0,1}^m ⧵ Rng(g), formula τ_b(g) naturally expressing b ∉ Rng(g) requires superpolynomial size P-proofs. One of the well-studied maps in the theory of proof complexity generators is Nisan-Wigderson generator. Razborov [A. A. {Razborov}, 2015] conjectured that if A is a suitable matrix and f is a NP∩CoNP function hard-on-average for 𝖯/poly, then NW_{f, A} is a hard proof complexity generator for Extended Frege. In this paper, we prove a form of Razborov’s conjecture for AC⁰-Frege. We show that for any symmetric NP∩CoNP function f that is exponentially hard for depth two AC⁰ circuits, NW_{f,A} is a hard proof complexity generator for AC⁰-Frege in a natural setting. As direct applications of this theorem, we show that: 1) For any f with the specified properties, τ_b(NW_{f,A}) (for a natural formalization) based on a random b and a random matrix A with probability 1-o(1) is a tautology and requires superpolynomial (or even exponential) AC⁰-Frege proofs. 2) Certain formalizations of the principle f_n ∉ (NP∩CoNP)/poly requires superpolynomial AC⁰-Frege proofs. These applications relate to two questions that were asked by Krajíček [J. {Krajíček}, 2019].
Cite as

Erfan Khaniki. Nisan-Wigderson Generators in Proof Complexity: New Lower Bounds. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 17:1-17:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{khaniki:LIPIcs.CCC.2022.17,
  author =	{Khaniki, Erfan},
  title =	{{Nisan-Wigderson Generators in Proof Complexity: New Lower Bounds}},
  booktitle =	{37th Computational Complexity Conference (CCC 2022)},
  pages =	{17:1--17:15},
  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.17},
  URN =		{urn:nbn:de:0030-drops-165799},
  doi =		{10.4230/LIPIcs.CCC.2022.17},
  annote =	{Keywords: Proof complexity, Bounded arithmetic, Bounded depth Frege, Nisan-Wigderson generators, Meta-complexity, Lower bounds}
}
Document
DOI: 10.4230/DagRep.7.2.1
Wildly Heterogeneous Post-CMOS Technologies Meet Software (Dagstuhl Seminar 17061)

Authors: Jerónimo Castrillón-Mazo, Tei-Wei Kuo, Heike E. Riel, and Matthias Lieber

Published in: Dagstuhl Reports, Volume 7, Issue 2 (2017)

Abstract
The end of exponential scaling in conventional CMOS technologies has been forecasted for many years by now. While advances in fabrication made it possible to reach limits beyond those predicted, the so anticipated end seems to be imminent today. The main goal of the seminar 17061 "Wildly Heterogeneous Post-CMOS Technologies Meet Software" was to discuss bridges between material research, hardware components and, ultimately, software for information processing systems. By bringing together experts from the individual fields and also researchers working interdisciplinarily across fields, the seminar helped to foster a mutual understanding about the challenges of advancing computing beyond current CMOS technology and to create long-term visions about a future hardware/software stack.
Cite as

Jerónimo Castrillón-Mazo, Tei-Wei Kuo, Heike E. Riel, and Matthias Lieber. Wildly Heterogeneous Post-CMOS Technologies Meet Software (Dagstuhl Seminar 17061). In Dagstuhl Reports, Volume 7, Issue 2, pp. 1-22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@Article{castrillonmazo_et_al:DagRep.7.2.1,
  author =	{Castrill\'{o}n-Mazo, Jer\'{o}nimo and Kuo, Tei-Wei and Riel, Heike E. and Lieber, Matthias},
  title =	{{Wildly Heterogeneous Post-CMOS Technologies Meet Software (Dagstuhl Seminar 17061)}},
  pages =	{1--22},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2017},
  volume =	{7},
  number =	{2},
  editor =	{Castrill\'{o}n-Mazo, Jer\'{o}nimo and Kuo, Tei-Wei and Riel, Heike E. and Lieber, Matthias},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.7.2.1},
  URN =		{urn:nbn:de:0030-drops-73499},
  doi =		{10.4230/DagRep.7.2.1},
  annote =	{Keywords: 3D integration, compilers, emerging post-CMOS circuit materials and technologies, hardware/software co-design, heterogeneous hardware, nanoelectronics}
}
  • Refine by Author
  • 1 Castrillón-Mazo, Jerónimo
  • 1 Khaniki, Erfan
  • 1 Kuo, Tei-Wei
  • 1 Lieber, Matthias
  • 1 Riel, Heike E.

  • Refine by Classification
  • 1 Theory of computation → Complexity theory and logic
  • 1 Theory of computation → Proof complexity

  • Refine by Keyword
  • 1 3D integration
  • 1 Bounded arithmetic
  • 1 Bounded depth Frege
  • 1 Lower bounds
  • 1 Meta-complexity
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2017
  • 1 2022

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