2 Search Results for "Iv�n, Szabolcs"

Document
DOI: 10.4230/LIPIcs.STACS.2017.23
Fractional Coverings, Greedy Coverings, and Rectifier Networks

Authors: Dmitry Chistikov, Szabolcs Iván, Anna Lubiw, and Jeffrey Shallit

Published in: LIPIcs, Volume 66, 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)

Abstract
A rectifier network is a directed acyclic graph with distinguished sources and sinks; it is said to compute a Boolean matrix M that has a 1 in the entry (i,j) iff there is a path from the j-th source to the i-th sink. The smallest number of edges in a rectifier network that computes M is a classic complexity measure on matrices, which has been studied for more than half a century. We explore two techniques that have hitherto found little to no applications in this theory. They build upon a basic fact that depth-2 rectifier networks are essentially weighted coverings of Boolean matrices with rectangles. Using fractional and greedy coverings (defined in the standard way), we obtain new results in this area. First, we show that all fractional coverings of the so-called full triangular matrix have cost at least n log n. This provides (a fortiori) a new proof of the tight lower bound on its depth-2 complexity (the exact value has been known since 1965, but previous proofs are based on different arguments). Second, we show that the greedy heuristic is instrumental in tightening the upper bound on the depth-2 complexity of the Kneser-Sierpinski (disjointness) matrix. The previous upper bound is O(n^{1.28}), and we improve it to O(n^{1.17}), while the best known lower bound is Omega(n^{1.16}). Third, using fractional coverings, we obtain a form of direct product theorem that gives a lower bound on unbounded-depth complexity of Kronecker (tensor) products of matrices. In this case, the greedy heuristic shows (by an argument due to Lovász) that our result is only a logarithmic factor away from the "full" direct product theorem. Our second and third results constitute progress on open problem 7.3 and resolve, up to a logarithmic factor, open problem 7.5 from a recent book by Jukna and Sergeev (in Foundations and Trends in Theoretical Computer Science (2013)).
Cite as

Dmitry Chistikov, Szabolcs Iván, Anna Lubiw, and Jeffrey Shallit. Fractional Coverings, Greedy Coverings, and Rectifier Networks. In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 66, pp. 23:1-23:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{chistikov_et_al:LIPIcs.STACS.2017.23,
  author =	{Chistikov, Dmitry and Iv\'{a}n, Szabolcs and Lubiw, Anna and Shallit, Jeffrey},
  title =	{{Fractional Coverings, Greedy Coverings, and Rectifier Networks}},
  booktitle =	{34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)},
  pages =	{23:1--23:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-028-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{66},
  editor =	{Vollmer, Heribert and Vall\'{e}e, Brigitte},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2017.23},
  URN =		{urn:nbn:de:0030-drops-70107},
  doi =		{10.4230/LIPIcs.STACS.2017.23},
  annote =	{Keywords: rectifier network, OR-circuit, biclique covering, fractional covering, greedy covering}
}
Document
DOI: 10.4230/OASIcs.CMN.2014.88
Mindreading, Privileged Access and Understanding Narratives

Authors: Szabolcs Kiss and Zoltán Jakab

Published in: OASIcs, Volume 41, 2014 Workshop on Computational Models of Narrative

Abstract
In this paper we first offer a task analysis of the false belief test including the bidirectional relationship between mindreading and language. Following this we present our theory concerning Quinian bootstrapping of the meaning of mental state terms and relate it to the task-analytic framework. Finally we present an experiment on ascribing privileged access through minimal narratives which is intended to serve as a test of our theory.
Cite as

Szabolcs Kiss and Zoltán Jakab. Mindreading, Privileged Access and Understanding Narratives. In 2014 Workshop on Computational Models of Narrative. Open Access Series in Informatics (OASIcs), Volume 41, pp. 88-105, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{kiss_et_al:OASIcs.CMN.2014.88,
  author =	{Kiss, Szabolcs and Jakab, Zolt\'{a}n},
  title =	{{Mindreading, Privileged Access and Understanding Narratives}},
  booktitle =	{2014 Workshop on Computational Models of Narrative},
  pages =	{88--105},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-71-2},
  ISSN =	{2190-6807},
  year =	{2014},
  volume =	{41},
  editor =	{Finlayson, Mark A. and Meister, Jan Christoph and Bruneau, Emile G.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.CMN.2014.88},
  URN =		{urn:nbn:de:0030-drops-46475},
  doi =		{10.4230/OASIcs.CMN.2014.88},
  annote =	{Keywords: mindreading, false belief attribution, privileged access, minimal narratives}
}
  • Refine by Author
  • 1 Chistikov, Dmitry
  • 1 Iván, Szabolcs
  • 1 Jakab, Zoltán
  • 1 Kiss, Szabolcs
  • 1 Lubiw, Anna
  • Show More...

  • Refine by Classification

  • Refine by Keyword
  • 1 OR-circuit
  • 1 biclique covering
  • 1 false belief attribution
  • 1 fractional covering
  • 1 greedy covering
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2014
  • 1 2017

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