• Corpus ID: 237396284

# ReLU Neural Networks of Polynomial Size for Exact Maximum Flow Computation

@inproceedings{Hertrich2021ReLUNN,
title={ReLU Neural Networks of Polynomial Size for Exact Maximum Flow Computation},
author={Christoph Hertrich and Leon Sering},
year={2021}
}
• Published 12 February 2021
• Computer Science
This paper studies the expressive power of artiﬁcial neural networks with rectiﬁed linear units. In order to study them as a model of real-valued computation, we introduce the concept of Max-Aﬃne Arithmetic Programs and show equivalence between them and neural networks concerning natural complexity measures. We then use this result to show that two fundamental combinatorial optimization problems can be solved with polynomial-size neural networks. First, we show that for any undirected graph…
1 Citations
• Computer Science
ArXiv
• 2022
The algorithmic problem of finding the optimal weights and biases for a two-layer fully connected neural network to a given set of data points is considered and it is shown that even very simple networks are difficult to train.
• Computer Science
• 2022
The algorithmic problem of finding the optimal weights and biases for a two-layer fully connected neural network to a given set of data points is considered and it is shown that even very simple networks are difficult to train.
{"ft_lang_label":"__label__en","ft_lang_prob":0.8591248,"math_prob":0.9410868,"size":5048,"snap":"2022-40-2023-06","text_gpt3_token_len":1051,"char_repetition_ratio":0.1461142,"word_repetition_ratio":0.20318726,"special_character_ratio":0.18997623,"punctuation_ratio":0.06896552,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.98439187,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2023-01-28T00:26:37Z\",\"WARC-Record-ID\":\"<urn:uuid:d95e3719-ee14-4f0d-97de-022ec76d6887>\",\"Content-Length\":\"374227\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:9420c2bd-7eb6-446d-9582-1568a3a5905c>\",\"WARC-Concurrent-To\":\"<urn:uuid:75d0aca8-f9e1-4a4e-bca4-864e554270e6>\",\"WARC-IP-Address\":\"18.154.227.127\",\"WARC-Target-URI\":\"https://www.semanticscholar.org/paper/ReLU-Neural-Networks-of-Polynomial-Size-for-Exact-Hertrich-Sering/82ad8d75a4f4dd22547722c95d5d670b4b72057a\",\"WARC-Payload-Digest\":\"sha1:HVVZD2KZVVFHTMSQWWVL3LKS5CY7UH2V\",\"WARC-Block-Digest\":\"sha1:CAUWRM5OJK2ZFQTZMXCOIFAMXZ2ZCNLD\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2023/CC-MAIN-2023-06/CC-MAIN-2023-06_segments_1674764499468.22_warc_CC-MAIN-20230127231443-20230128021443-00820.warc.gz\"}"}