Conference item icon

Conference item

Fractional coverings, greedy coverings, and rectifier networks

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 jth source to the ith 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...

Expand abstract
Publication status:
Published
Peer review status:
Peer reviewed
Version:
Publisher's version

Actions


Access Document


Files:
Publisher copy:
10.4230/LIPIcs.STACS.2017.23

Authors


More by this author
Institution:
University of Oxford
Department:
Oxford, MPLS, Computer Science
Role:
Author
Publisher:
Schloss Dagstuhl Publisher's website
Volume:
66
Pages:
23:1-23:14
Publication date:
2017-02-24
Acceptance date:
2016-11-12
DOI:
ISSN:
1868-8969
Pubs id:
pubs:681962
URN:
uri:d051af55-422b-4d8e-b1bd-58ea53df395b
UUID:
uuid:d051af55-422b-4d8e-b1bd-58ea53df395b
Local pid:
pubs:681962

Terms of use


Metrics


Views and Downloads






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP