3 Search Results for "Brown, Paul"

Document
DOI: 10.4230/LIPIcs.CCC.2020.28
Exponential Resolution Lower Bounds for Weak Pigeonhole Principle and Perfect Matching Formulas over Sparse Graphs

Authors: Susanna F. de Rezende, Jakob Nordström, Kilian Risse, and Dmitry Sokolov

Published in: LIPIcs, Volume 169, 35th Computational Complexity Conference (CCC 2020)

Abstract
We show exponential lower bounds on resolution proof length for pigeonhole principle (PHP) formulas and perfect matching formulas over highly unbalanced, sparse expander graphs, thus answering the challenge to establish strong lower bounds in the regime between balanced constant-degree expanders as in [Ben-Sasson and Wigderson '01] and highly unbalanced, dense graphs as in [Raz '04] and [Razborov '03, '04]. We obtain our results by revisiting Razborov’s pseudo-width method for PHP formulas over dense graphs and extending it to sparse graphs. This further demonstrates the power of the pseudo-width method, and we believe it could potentially be useful for attacking also other longstanding open problems for resolution and other proof systems.
Cite as

Susanna F. de Rezende, Jakob Nordström, Kilian Risse, and Dmitry Sokolov. Exponential Resolution Lower Bounds for Weak Pigeonhole Principle and Perfect Matching Formulas over Sparse Graphs. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 28:1-28:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{derezende_et_al:LIPIcs.CCC.2020.28,
  author =	{de Rezende, Susanna F. and Nordstr\"{o}m, Jakob and Risse, Kilian and Sokolov, Dmitry},
  title =	{{Exponential Resolution Lower Bounds for Weak Pigeonhole Principle and Perfect Matching Formulas over Sparse Graphs}},
  booktitle =	{35th Computational Complexity Conference (CCC 2020)},
  pages =	{28:1--28:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-156-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{169},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2020.28},
  URN =		{urn:nbn:de:0030-drops-125804},
  doi =		{10.4230/LIPIcs.CCC.2020.28},
  annote =	{Keywords: proof complexity, resolution, weak pigeonhole principle, perfect matching, sparse graphs}
}
Document
DOI: 10.4230/DagSemProc.09291.7
Autonomy, Signature and Creativity

Authors: Paul Brown

Published in: Dagstuhl Seminar Proceedings, Volume 9291, Computational Creativity: An Interdisciplinary Approach (2009)

Abstract
One of the key themes that emerged from the formal investigations of art and aesthetics during the 20th century was that of the autonomous artwork. The goal of an artwork that was not just self-referential but also self-creating found renewed vigour in the work of the systems and conceptual artists and especially those who were early adopters of the then-new technology of artificial intelligence (AI). A key problem is that of signature: at what point can we claim that an artwork has its own distinct signature? My own work in this area began in the 1960’s with an early, and in retrospect, naive assumption. At that time art was still based on the concept of engagement with the materiality of the medium. I suggested that using a symbolic language to initiate a process would distance me far enough from the output of that process for it to have the potential of developing its own intrinsic qualities including a unique signature. By the 1990s it had become obvious that this approach had failed. Complementary research in many fields had demonstrated that the signatures of life were robust and strongly relativistic. The myriad bonds that define a signature are embedded in even the simplest symbol system and any attempt to create autonomy by formal construction is unlikely to succeed. During this same period a group of biologically inspired computational methods were revisited after several decades of neglect; evolutionary, adaptive and learning systems suggested a “bottom up” approach to the problem. If it’s not possible to design an autonomous agency then can we instead make a system that evolves, learns for itself and eventually has the potential of displaying autonomy as an emergent property? The DrawBots project is an attempt to apply these computational methods to the problem of artistic autonomy. It is an example of a strong art-science collaboration where all the disciplines involved have a significant investment in the project and its themes.
Cite as

Paul Brown. Autonomy, Signature and Creativity. In Computational Creativity: An Interdisciplinary Approach. Dagstuhl Seminar Proceedings, Volume 9291, pp. 1-7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{brown:DagSemProc.09291.7,
  author =	{Brown, Paul},
  title =	{{Autonomy, Signature and Creativity}},
  booktitle =	{Computational Creativity: An Interdisciplinary Approach},
  pages =	{1--7},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{9291},
  editor =	{Margaret Boden and Mark D'Inverno and Jon McCormack},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.09291.7},
  URN =		{urn:nbn:de:0030-drops-22047},
  doi =		{10.4230/DagSemProc.09291.7},
  annote =	{Keywords: Computational creativity, autonomous art, signature}
}
Document
DOI: 10.4230/DagSemProc.09291.22
Notes from the Discussion Group on "Evaluation"

Authors: David Brown

Published in: Dagstuhl Seminar Proceedings, Volume 9291, Computational Creativity: An Interdisciplinary Approach (2009)

Abstract
Group Members: Harold Cohen, Maggie Boden, Dave Brown, Paul Brown, Oliver Deussen, Philip Galanter. These notes represent approximately what was discussed by the group members over a period of several hours over two days. There has been some attempt to organize the material, but little attempt to expand it to make it coherent—we rambled, so do the notes. The notes, and this report, were recorded, organized, and elaborated into this form by Dave Brown.
Cite as

David Brown. Notes from the Discussion Group on "Evaluation". In Computational Creativity: An Interdisciplinary Approach. Dagstuhl Seminar Proceedings, Volume 9291, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{brown:DagSemProc.09291.22,
  author =	{Brown, David},
  title =	{{Notes from the Discussion Group on "Evaluation"}},
  booktitle =	{Computational Creativity: An Interdisciplinary Approach},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{9291},
  editor =	{Margaret Boden and Mark D'Inverno and Jon McCormack},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.09291.22},
  URN =		{urn:nbn:de:0030-drops-22128},
  doi =		{10.4230/DagSemProc.09291.22},
  annote =	{Keywords: Evaluation, art, artistic, creativity}
}
  • Refine by Author
  • 1 Brown, David
  • 1 Brown, Paul
  • 1 Nordström, Jakob
  • 1 Risse, Kilian
  • 1 Sokolov, Dmitry
  • Show More...

  • Refine by Classification
  • 1 Theory of computation → Proof complexity

  • Refine by Keyword
  • 1 Computational creativity
  • 1 Evaluation
  • 1 art
  • 1 artistic
  • 1 autonomous art
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 2 2009
  • 1 2020

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