Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with combinatorial algorithms:
TR06-053 | 6th April 2006
Eldar Fischer, Orly Yahalom

Testing Convexity Properties of Tree Colorings

A coloring of a graph is {\it convex} if it
induces a partition of the vertices into connected subgraphs.
Besides being an interesting property from a theoretical point of
view, tests for convexity have applications in various areas
involving large graphs. Our results concern the important subcase
of testing for ... more >>>

TR17-098 | 28th May 2017
Raman Arora, Amitabh Basu , Poorya Mianjy, Anirbit Mukherjee

Understanding Deep Neural Networks with Rectified Linear Units

Revisions: 2

In this paper we investigate the family of functions representable by deep neural networks (DNN) with rectified linear units (ReLU). We give the first-ever polynomial time (in the size of data) algorithm to train to global optimality a ReLU DNN with one hidden layer, assuming the input dimension and number ... more >>>

ISSN 1433-8092 | Imprint