Skip to content Skip to navigation
University of Warwick
  • Study
  • |
  • Research
  • |
  • Business
  • |
  • Alumni
  • |
  • News
  • |
  • About

University of Warwick
Publications service & WRAP

Highlight your research

  • WRAP
    • Home
    • Search WRAP
    • Browse by Warwick Author
    • Browse WRAP by Year
    • Browse WRAP by Subject
    • Browse WRAP by Department
    • Browse WRAP by Funder
    • Browse Theses by Department
  • Publications Service
    • Home
    • Search Publications Service
    • Browse by Warwick Author
    • Browse Publications service by Year
    • Browse Publications service by Subject
    • Browse Publications service by Department
    • Browse Publications service by Funder
  • Help & Advice
University of Warwick

The Library

  • Login
  • Admin

Fractional coverings, greedy coverings, and rectifier networks

Tools
- Tools
+ Tools

Chistikov, Dmitry, Iván, S., Lubiw, A. and Shallit, J. (2017) Fractional coverings, greedy coverings, and rectifier networks. In: 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017), Hannover, Germany, 8-11 Mar 2017. Published in: Leibniz International Proceedings in Informatics, LIPIcs, 66 23:1-23:14. ISBN 9783959770286. ISSN 1868-8969.

[img]
Preview
PDF
WRAP-fractional-coverings-greedy-coverings-rectifier-networks-Chistikov-2018.pdf - Published Version - Requires a PDF viewer.
Available under License Creative Commons Attribution 4.0.

Download (955Kb) | Preview
Official URL: https://doi.org/10.4230/LIPIcs.STACS.2017.23

Request Changes to record.

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).

Item Type: Conference Item (Paper)
Subjects: Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software
Divisions: Faculty of Science > Computer Science
Library of Congress Subject Headings (LCSH): Directed graphs, Boolean matrices
Journal or Publication Title: Leibniz International Proceedings in Informatics, LIPIcs
Publisher: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
ISBN: 9783959770286
ISSN: 1868-8969
Official Date: 2017
Dates:
DateEvent
2017Published
Volume: 66
Page Range: 23:1-23:14
Status: Peer Reviewed
Publication Status: Published
Access rights to Published version: Open Access
RIOXX Funder/Project Grant:
Project/Grant IDRIOXX Funder NameFunder ID
ImPACTEuropean Research Councilhttp://viaf.org/viaf/130022607
648701European Research Councilhttp://viaf.org/viaf/130022607
108448Hungary. Nemzeti Kutatási, Fejlesztési és Innovációs Hivatal [National Research, Development and Innovation Office]UNSPECIFIED
Conference Paper Type: Paper
Title of Event: 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)
Type of Event: Conference
Location of Event: Hannover, Germany
Date(s) of Event: 8-11 Mar 2017
Related URLs:
  • Organisation
  • Other Repository
  • Open Access File

Request changes or add full text files to a record

Repository staff actions (login required)

View Item View Item

Downloads

Downloads per month over past year

View more statistics

twitter

Email us: wrap@warwick.ac.uk
Contact Details
About Us