Pith. sign in

REVIEW 3 major objections 4 minor 46 references

New Complexity-Theoretic Frontiers of Tractability for Neural Network Training

T0 review · 3 major / 4 minor · reviewed 2026-08-01 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read This paper finds two structural conditions under which optimally training a neural network is polynomial-time solvable: ReLU nets whose hidden neurons each feed exactly one successor, and linear nets that admit an untangling.

desk verdict The ReLU out-degree-1 result is real and worth engaging with; the linear part has the right idea but the auxiliary algorithms are sloppier than the main theorem. read the letter →

arxiv 2607.20811 v1 pith:3U67TQ5H submitted 2026-07-23 cs.LG cs.DS

Cornelius Brand , Robert Ganian , Mathis Rocton This is my paper · ORCID
classification cs.LGcs.DS MSC 68Q1768Q2568T07
keywords neuralnetworktrainingReLUactivationlinearcomputationalcomplexitypolynomial-timealgorithmuntanglinghyperplanepartitiontractability
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Optimal neural network training is known to be intractable in general, and even for small ReLU and linear networks the exact boundary of tractability is open. This paper establishes two new positive results. For ReLU networks in which every hidden neuron has out-degree exactly one, it gives an algorithm that provably finds a globally optimal weight and bias assignment in time |D|^{O(n·w·2^w)}·poly(L), matching known lower bounds in the simplest cases. For linear networks, it introduces the notion of an untangling—a structural decomposition of the architecture into connected blocks anchored at inputs and outputs—and shows that whenever one is given (or can be computed), the training problem reduces to a polynomial-time quadratic program. A consequence is that every constant-size ReLU architecture can be replaced by a same-depth architecture that is at least as expressive and trainable to optimality in polynomial time.

What carries the argument

The central objects are two. For ReLU nets: the proof that in out-degree-1 architectures every deep edge weight can be normalized to {−1, 1} (by absorbing |a_uw| into incoming weights and bias), plus an LP-extreme-point enumeration (Lemma 3) that lists all hyperplane partitions of the training set in |D|^{O(n)} time—together these shrink the search to a finite branching over partitions and signs, each branch a quadratic program. For linear nets: the 'untangling', a partition of the architecture vertices into connected blocks, one anchored at each input as its unique source and each output as its unique sink, with block adjacencies mirroring input–output reachability; this guarantees the trai

What would settle it

Construct a finite point set D in R^n with points in degenerate position (collinear or on candidate separating hyperplanes) and check whether the LP-extreme-point procedure of Lemma 3 enumerates every separable partition; if any partition is missing, or if the number of partitions exceeds |D|^{O(n)}, then Theorem 5's search is not exhaustive. Alternatively, run the Theorem 5 algorithm on a small out-degree-1 ReLU network with a brute-force-verifiable optimum and compare losses.

Watch

Extended reading notes

Core claim

The paper's central claim is that two previously open or intractable-feeling cases of exact neural network training are actually polynomial-time solvable. Theorem 5 states that for any constant-size ReLU network whose hidden neurons all have out-degree exactly 1, an optimal assignment of all weights and biases can be computed in |D|^{O(n·w·2^w)}·poly(L); the proof first shows such weights can be assumed to be ±1 on deep edges, then branches over the finite set of ways each neuron can split the data set into active and dead regions, solving a quadratic program per configuration. Theorem 12 shows that a linear network provided with an untangling can be trained in poly(|D|+|V|) time by reducing

Load-bearing premise

The ReLU tractability result hinges on Lemma 3, which asserts that all hyperplane partitions of a finite point set in R^n can be enumerated in |D|^{O(n)} time via an LP extreme-point argument; if that enumeration is incomplete for degenerate configurations (e.g., points lying exactly on a separating hyperplane), the branching algorithm could miss optimal solutions.

Editorial extensions

If this is right

  • Constant-size ReLU networks with out-degree-1 hidden neurons—including multi-output, multi-layer, and mixed ReLU/linear cases—are optimally trainable in polynomial time, with running time essentially optimal for single-neuron architectures.
  • Every constant-size ReLU architecture can be transformed into a same-depth architecture that is at least as expressive and is polynomially trainable; thus width, not depth, is what the blow-up trades.
  • Linear networks with an untangling—which include single-output and single-input networks and many others—are polynomially trainable, and untanglings can be computed in linear time for architectures with constant hidden neurons or bounded treewidth.
  • Finding an untangling is NP-hard in general, so the tractability for linear networks is conditional on the presence of this structure or on structural restrictions that make it computable.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The hyperplane-partition enumeration lemma is likely to be reusable beyond this paper: any finite-point-set optimization over piecewise-linear activations that depends only on which side of a hyperplane each point falls could be tackled the same way, provided the enumeration is indeed complete on degenerate inputs.
  • The untangling condition reads as a 'data throughput' parameter: it captures how cleanly information flows from inputs to outputs. If extended, it could lead to a hierarchy of tractable architectures for linear training beyond the first non-trivial class identified here, e.g., by parameterizing by the size of the smallest backdoor.
  • The blow-up construction suggests that for constant-size ReLU networks, improper learning—training an enlarged but equally expressive architecture—is no worse than proper training; an empirical test on small nets could show whether the enlarged architectures train better in practice and whether the depth-preserving transformation affects generalization.
  • The running time |D|^{O(n·w·2^w)} means the algorithm is practical only for very small n, w; an open direction implicit in the paper is whether the 2^w factor can be avoided or whether out-degree >1 is genuinely harder.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

Summary. The paper studies exact training of neural networks with ReLU and linear activations. It claims three main contributions. First, it proves that for networks in which every hidden neuron has out-degree exactly 1 and the number of inputs n and non-input nodes w are constants, RELU-NNT can be solved exactly in time |D|^{O(n·w·2^w)}·poly(L), improving on the single-hidden-layer/single-output algorithm of Arora et al. and Boob et al. The proof discretizes deep weights to ±1, enumerates possible activation partitions of the training data using a hyperplane-separation lemma, and solves a constrained least-squares problem for each branch. Second, it shows that every constant-size ReLU architecture can be transformed into a same-depth "blown-up" architecture that is at least as expressive and trainable in polynomial time. Third, for linear networks it introduces the notion of an untangling, proves that LIN-NNT is polynomial-time solvable when an untangling is provided, and gives algorithms to compute untanglings for architectures with constant hidden-neuron count or constant treewidth. The paper also proves NP-hardness of computing untanglings in general.

Significance. If corrected, the results would be a notable advance: exact training of ReLU networks beyond the shallow single-output case, and the first positive algorithmic upper bound for LIN-NNT with a potentially large number of inputs but structured architecture. The paper is generally careful and self-contained, and it explicitly flags a gap in the analogous enumeration claim of Arora et al.; the sign-normalization lemma and the reduction of LIN-NNT to constrained least squares are elegant and appear sound. The main proofs are not circular and rely only on standard results. However, the current manuscript contains a load-bearing gap in the enumeration lemma, an overclaim in the abstract, and a flawed MSOL encoding in the constant-treewidth untangling theorem; these need correction before the claims can be accepted.

major comments (3)
  1. [Section 4, Lemma 3] The proof asserts that a vertex of the LP in R^{n+2} is determined by a selection of at most n points. This is false: a vertex requires n+2 independent tight constraints, and in the absence of active box constraints it can have n+2 point constraints; even when one box constraint is active (which is forced at an optimum), n+1 point constraints are possible. Concretely, for n=1 and D={0,2}, the strictly separable partition A={2}, B={0} has maximum-margin vertex v=1, b=1, r=1, whose active constraints are v=1, 2=b+r, 0=b-r — two point constraints, not at most one. The algorithm as written enumerates only choices with at most one point and therefore would not output this partition. Since Lemma 4 and Theorem 5 branch over the partitions produced by Lemma 3, a missed partition can exclude the global optimum, so the correctness proof of Theorem 5 is incomplete. The fix is to enumerate up to n+2
  2. [Abstract and Theorems 5, 10] The abstract states 'polynomial-time tractability of all architectures where hidden neurons have an out-degree of 1' with no constant-size qualifier. Theorem 5's running time is |D|^{O(n·w·2^w)}·poly(L), which is polynomial only when n and w are treated as fixed constants. Without that qualifier the statement is false: with n part of the input, RELU-NNT is NP-hard even for a single ReLU neuron (Goel et al., 2021; Froese et al., 2022). Similarly, Theorem 10's running time |D|^{O(n·τ·2^τ)} is polynomial only when the architecture is constant-size. The introduction states the qualifier correctly, but the abstract and the theorem statements need to be aligned; otherwise the main claim is overclaimed.
  3. [Section 6, Theorem 15] The MSOL formula Φ(X) as written cannot encode untanglings with singleton blocks. A singleton input block C_i={x_i} or output block D_j={y_j} contributes no edges to the union X of branchings, hence does not appear as a component Y satisfying CC(Y,X); the reachability conjunct then never requires the edge between that block and the opposite block, so the formula can accept invalid edge sets. Singleton blocks are not pathological: in the two-input one-hidden-one-output example with edges x1→h, x2→h, h→y, the natural untangling has C1={x1}, C2={x2}, D1={h,y}. Additionally, the definitions of InB and OutB in the bullet list appear swapped: an in-branching has a unique sink (not source), and an out-branching has a unique source (not sink); the formula then uses InB(Y)∧OutB(Z) where the proof text's explanation requires an out-branching on Y and an in-branching on Z. These problems are not me
minor comments (4)
  1. [Section 4, Lemma 3] Notation is confusing: v is used both for the normal vector and for data points in B. Use distinct symbols, e.g., w for the normal vector and d for data points.
  2. [Section 4, Lemma 4] In the definition of the set P, the index j is used both for the number of equivalence classes and for the enumeration of p1,...,pj; this should be cleaned up.
  3. [Section 6, Theorem 13] The proof is terse at the point where vertices from L2 are moved out of a D_j block. The 'by symmetry' argument should be expanded, since the current text does not fully justify that the modified partition still satisfies the only-source/only-sink conditions.
  4. [Section 4, Theorem 5] The statement says 'global optimal solution' but the use of the ellipsoid method for the quadratic program is only sketched. Please specify the computational model and bit complexity assumptions (e.g., rational data, polynomial in L) so that the claim is unambiguous.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the algorithmic results are self-contained and rely only on standard external tools; the flagged Lemma 3 concern is a correctness issue, not circularity.

full rationale

The paper's derivation chain is self-contained rather than circular. The ReLU tractability result (Theorem 5) is built from Lemma 1-2 (a self-contained normalization argument using homogeneity of ReLU), Lemma 3-4 (a self-contained enumeration of hyperplane partitions of a finite point set), and a final reduction to convex quadratic programming solved by the ellipsoid method (Kozlov et al., 1979; Pang, 1983). Lemma 3 is proved in the paper rather than imported from the authors' own work; indeed, the paper explicitly criticizes the analogous claim in Arora et al. (2018) as incomplete, showing that it is not relying on that prior argument as an authority. The linear-network result (Theorem 12) reduces LIN-NNT, given an untangling, to a quadratic program whose variables are the untangling-selected path products, and the proof explicitly argues equality of optimal values in both directions; this is a constructive reduction, not a restatement of the problem. The blow-up construction (Section 5) is proved function-preserving in Lemma 7 and only then combined with Theorem 5, so no target result is used as an input. Citations to the authors' own prior work (e.g., Ganian et al. 2018, 2022; Brand et al. 2021) appear only as contextual examples in the introduction and are not load-bearing. The skeptical concern about Lemma 3—that extreme-point enumeration might miss separable partitions realized only by non-vertex separating hyperplanes—is a potential correctness gap in the proof, not a circularity: even if valid, it does not amount to an input being equivalent to an output by construction. Accordingly, the circularity score is 0.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

No free parameters are fitted. The load-bearing external inputs are standard algorithmic theorems (ellipsoid for convex QP, Courcelle's theorem), a standard NP-hardness source, and the problem's formalization (DAG architecture, ReLU/linear activations, ℓ2 loss, rational data). The new concepts (out-degree-1 condition, untangling, blow-up) are defined and proved within the paper rather than assumed.

assumptions (5)
  • domain assumption Data points are encoded with L bits (rational inputs).
    The QP/ellipsoid algorithms require finite-precision input; the paper assumes data are encoded using L bits and runtimes include poly(L). This is standard for the NNT formalization.
  • standard math Convex quadratic programming is solvable in polynomial time via the ellipsoid method (Kozlov et al. 1979).
    Theorem 5 and Theorem 12 reduce to convex QP; if this were not polynomial-time, the tractability claims would fail. It is an external standard result.
  • standard math Courcelle's theorem for MSOL on bounded-treewidth graphs (Theorem 15).
    Used to compute untanglings on constant-treewidth architectures; if the MSOL encoding is wrong or Courcelle does not apply, that auxiliary result fails.
  • standard math NP-hardness of DOMINATING SET 3-PARTITIONING (Heggernes & Telle 1998).
    Used in the NP-hardness reduction for computing untanglings; this is an external complexity-theoretic result.
  • domain assumption The architecture is a directed acyclic graph with input, output, and hidden neurons; activations are ReLU or linear; loss is ℓ2-squared.
    The problem definition; the results are specific to these activations, loss, and graph model.

how reviews work

0 comments
Cite this review

Pith. "Pith review of New Complexity-Theoretic Frontiers of Tractability for Neural Network Training." pith.science (2026). https://pith.science/paper/3U67TQ5H

@misc{pith2026260720811,
  author       = {Pith},
  title        = {Pith review of: New Complexity-Theoretic Frontiers of Tractability for Neural Network Training},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/3U67TQ5H}},
  note         = {Machine review of arXiv:2607.20811}
}
abstract

In spite of the fundamental role of neural networks in contemporary machine learning research, our understanding of the computational complexity of optimally training neural networks remains incomplete even when dealing with the simplest kinds of activation functions. Indeed, while there has been a number of very recent results that establish ever-tighter lower bounds for the problem under linear and ReLU activation functions, less progress has been made towards the identification of novel polynomial-time tractable network architectures. In this article we obtain novel algorithmic upper bounds for training linear- and ReLU-activated neural networks to optimality which push the boundaries of tractability for these problems beyond the previous state of the art. In particular, for ReLU networks we establish the polynomial-time tractability of all architectures where hidden neurons have an out-degree of $1$, improving upon the previous algorithm of Arora, Basu, Mianjy and Mukherjee. On the other hand, for networks with linear activation functions we identify the first non-trivial polynomial-time solvable class of networks by obtaining an algorithm that can optimally train network architectures satisfying a novel data throughput condition.

Figures

Figures reproduced from arXiv: 2607.20811 by the authors.

Figure 1
Figure 1. A neural network with two lay￾ers of hidden, ReLU-activated neurons, computing a function f : R 4 → R 3 . Neural networks are a prominent tool in contemporary machine learning, one which has found ubiquitous appli￾cations throughout modern computer science (Goodfellow et al., 2016). A neural network (cf [PITH_FULL_IMAGE:figures/full_fig_p001_1.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

46 extracted references · 9 canonical work pages

  1. [1]

    Training neural networks is er-complete

    Abrahamsen, M., Kleist, L., and Miltzow, T. Training neural networks is er-complete. In Ranzato, M., Beygelzimer, A., Dauphin, Y. N., Liang, P., and Vaughan, J. W. (eds.), Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual, pp.\ 18293--18306, 202...

    2021

  2. [2]

    Understanding deep neural networks with rectified linear units

    Arora, R., Basu, A., Mianjy, P., and Mukherjee, A. Understanding deep neural networks with rectified linear units. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 - May 3, 2018, Conference Track Proceedings . OpenReview.net, 2018. URL https://openreview.net/forum?id=B1J\_rgWRW

    2018

  3. [3]

    Training Fully Connected Neural Networks is $\exists\mathbb{R}$-Complete

    Bertschinger, D., Hertrich, C., Jungeblut, P., Miltzow, T., and Weber, S. Training fully connected neural networks is \( \) r-complete. CoRR, abs/2204.01368, 2022. doi:10.48550/arXiv.2204.01368. URL https://doi.org/10.48550/arXiv.2204.01368

    work page Pith review arXiv doi:10.48550/arxiv.2204.01368 2022

  4. [4]

    Bodlaender, H. L. Treewidth of graphs. In Encyclopedia of Algorithms, pp.\ 2255--2257. 2016. doi:10.1007/978-1-4939-2864-4\_431. URL https://doi.org/10.1007/978-1-4939-2864-4\_431

    doi:10.1007/978-1-4939-2864-4 2016

  5. [5]

    S., and Lan, G

    Boob, D., Dey, S. S., and Lan, G. Complexity of training relu neural network. Discret. Optim., 44 0 (Part): 0 100620, 2022. doi:10.1016/j.disopt.2020.100620. URL https://doi.org/10.1016/j.disopt.2020.100620

    arXiv 2022

  6. [6]

    Parameterized algorithms for milps with small treedepth

    Brand, C., Kouteck \' y , M., and Ordyniak, S. Parameterized algorithms for milps with small treedepth. In Thirty-Fifth AAAI Conference on Artificial Intelligence, AAAI 2021, Thirty-Third Conference on Innovative Applications of Artificial Intelligence, IAAI 2021, The Eleventh Symposium on Educational Advances in Artificial Intelligence, EAAI 2021, Virtua...

    2021

  7. [7]

    Bulatov, A. A. A dichotomy theorem for nonuniform csps. In Umans, C. (ed.), 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017 , pp.\ 319--330. IEEE Computer Society, 2017. doi:10.1109/FOCS.2017.37. URL https://doi.org/10.1109/FOCS.2017.37

    doi:10.1109/focs.2017.37 2017

  8. [8]

    On the expressive power of deep learning: A tensor analysis

    Cohen, N., Sharir, O., and Shashua, A. On the expressive power of deep learning: A tensor analysis. In Feldman, V., Rakhlin, A., and Shamir, O. (eds.), Proceedings of the 29th Conference on Learning Theory, COLT 2016, New York, USA, June 23-26, 2016 , volume 49 of JMLR Workshop and Conference Proceedings , pp.\ 698--728. JMLR.org, 2016. URL http://proceed...

    2016

Show all 46 references
  1. [9]

    The monadic second-order logic of graphs

    Courcelle, B. The monadic second-order logic of graphs. i. recognizable sets of finite graphs. Inf. Comput., 85 0 (1): 0 12--75, 1990. doi:10.1016/0890-5401(90)90043-H. URL https://doi.org/10.1016/0890-5401(90)90043-H

    1990 doi

  2. [10]

    and Engelfriet, J

    Courcelle, B. and Engelfriet, J. Graph Structure and Monadic Second-Order Logic - A Language-Theoretic Approach , volume 138 of Encyclopedia of mathematics and its applications. Cambridge University Press, 2012. ISBN 978-0-521-89833-1. URL http://www.cambridge.org/fr/knowledge...

    2012

  3. [11]

    and Pillow, J

    Cowley, B. and Pillow, J. W. High-contrast "gaudy" images improve the training of deep neural network models of visual cortex. In Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M., and Lin, H. (eds.), Advances in Neural Information Processing Systems 33: Annual Conference o...

    2020

  4. [12]

    V., Panolan, F., and Simonov, K

    Dahiya, Y., Fomin, F. V., Panolan, F., and Simonov, K. Fixed-parameter and approximation algorithms for PCA with outliers. In Meila, M. and Zhang, T. (eds.), Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event , volum...

    2021

  5. [13]

    S., Wang, G., and Xie, Y

    Dey, S. S., Wang, G., and Xie, Y. Approximation algorithms for training one-node relu neural networks. IEEE Trans. Signal Process. , 68: 0 6696--6706, 2020. doi:10.1109/TSP.2020.3039360. URL https://doi.org/10.1109/TSP.2020.3039360

    2020

  6. [14]

    Graph Theory, 4th Edition, volume 173 of Graduate texts in mathematics

    Diestel, R. Graph Theory, 4th Edition, volume 173 of Graduate texts in mathematics. Springer, 2012. ISBN 978-3-642-14278-9

    2012

  7. [15]

    Constructing arrangements of lines and hyperplanes with applications

    Edelsbrunner, H., O'Rourke, J., and Seidel, R. Constructing arrangements of lines and hyperplanes with applications. SIAM J. Comput. , 15 0 (2): 0 341--363, 1986. doi:10.1137/0215024. URL https://doi.org/10.1137/0215024

    1986 doi

  8. [16]

    and Shamir, O

    Eldan, R. and Shamir, O. The power of depth for feedforward neural networks. In Feldman, V., Rakhlin, A., and Shamir, O. (eds.), Proceedings of the 29th Conference on Learning Theory, COLT 2016, New York, USA, June 23-26, 2016 , volume 49 of JMLR Workshop and Conference Procee...

    2016

  9. [17]

    and Tardos, \'E

    Frank, A. and Tardos, \'E . An application of simultaneous diophantine approximation in combinatorial optimization. 7 0 (1): 0 49--65, 1987

    1987

  10. [18]

    and Hertrich, C

    Froese, V. and Hertrich, C. Training neural networks is np-hard in fixed dimension. In Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurIPS 2023, 2023. URL https://doi.org/10.48550/arXiv.2303.17045. to appear

    2023 doi arXiv

  11. [19]

    The computational complexity of relu network training parameterized by data dimensionality

    Froese, V., Hertrich, C., and Niedermeier, R. The computational complexity of relu network training parameterized by data dimensionality. J. Artif. Intell. Res., 74: 0 1775--1790, 2022. doi:10.1613/jair.1.13547. URL https://doi.org/10.1613/jair.1.13547

    2022 doi

  12. [20]

    and Korchemna, V

    Ganian, R. and Korchemna, V. The complexity of bayesian network learning: Revisiting the superstructure. In Ranzato, M., Beygelzimer, A., Dauphin, Y. N., Liang, P., and Vaughan, J. W. (eds.), Advances in Neural Information Processing Systems 34: Annual Conference on Neural Inf...

    2021

  13. [21]

    and Ordyniak, S

    Ganian, R. and Ordyniak, S. Solving integer linear programs by exploiting variable-constraint interactions: A survey. Algorithms, 12 0 (12): 0 248, 2019. doi:10.3390/a12120248. URL https://doi.org/10.3390/a12120248

    2019 doi

  14. [22]

    A., Ordyniak, S., and Szeider, S

    Ganian, R., Kanj, I. A., Ordyniak, S., and Szeider, S. Parameterized algorithms for the matrix completion problem. In Dy, J. G. and Krause, A. (eds.), Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsm \" a ssan, Stockholm, Sweden, Jul...

    2018

  15. [23]

    The complexity of k-means clustering when little is known

    Ganian, R., Hamm, T., Korchemna, V., Okrasa, K., and Simonov, K. The complexity of k-means clustering when little is known. In Chaudhuri, K., Jegelka, S., Song, L., Szepesv \' a ri, C., Niu, G., and Sabato, S. (eds.), International Conference on Machine Learning, ICML 2022, 17...

    2022

  16. [24]

    Adaptive convolutional relus

    Gao, H., Cai, L., and Ji, S. Adaptive convolutional relus. In The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, The Thirty-Second Innovative Applications of Artificial Intelligence Conference, IAAI 2020, The Tenth AAAI Symposium on Educational Advances i...

    2020

  17. [25]

    R., Manurangsi, P., and Reichman, D

    Goel, S., Klivans, A. R., Manurangsi, P., and Reichman, D. Tight hardness results for training depth-2 relu networks. In Lee, J. R. (ed.), 12th Innovations in Theoretical Computer Science Conference, ITCS 2021, January 6-8, 2021, Virtual Conference , volume 185 of LIPIcs, pp.\...

    2021 doi

  18. [26]

    Deep Learning

    Goodfellow, I., Bengio, Y., and Courville, A. Deep Learning. MIT Press, 2016. URL http://www.deeplearningbook.org/

    2016

  19. [27]

    and Komusiewicz, C

    Gr \" u ttemeier, N. and Komusiewicz, C. Learning bayesian networks under sparsity constraints: A parameterized complexity analysis. J. Artif. Intell. Res., 74: 0 1225--1267, 2022. doi:10.1613/jair.1.13138. URL https://doi.org/10.1613/jair.1.13138

    2022 doi

  20. [28]

    Lower bounds on the depth of integral relu neural networks via lattice polytopes

    Haase, C., Hertrich, C., and Loho, G. Lower bounds on the depth of integral relu neural networks via lattice polytopes. In The Eleventh International Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023 . OpenReview.net, 2023. URL https://openreview...

    2023

  21. [29]

    Harding, E. F. The number of partitions of a set of n points in k dimensions induced by hyperplanes. Proceedings of the Edinburgh mathematical society, 15 0 (4): 0 285--289, 1967

    1967

  22. [30]

    and Telle, J

    Heggernes, P. and Telle, J. A. Partitioning graphs into generalized dominating sets. Nordic J. of Computing, 5 0 (2): 0 128–142, jun 1998. ISSN 1236-6064

    1998

  23. [31]

    Facets of neural network complexity

    Hertrich, C. Facets of neural network complexity. PhD thesis, Technical University of Berlin, Germany, 2022. URL https://nbn-resolving.org/urn:nbn:de:101:1-2022033001583912451077

    2022

  24. [32]

    D., and Skutella, M

    Hertrich, C., Basu, A., Summa, M. D., and Skutella, M. Towards lower bounds on the depth of relu neural networks. In Ranzato, M., Beygelzimer, A., Dauphin, Y. N., Liang, P., and Vaughan, J. W. (eds.), Advances in Neural Information Processing Systems 34: Annual Conference on N...

    2021

  25. [33]

    Minkowski's convex body theorem and integer programming

    Kannan, R. Minkowski's convex body theorem and integer programming. Math. Oper. Res., 12 0 (3): 0 415--440, 1987

    1987

  26. [34]

    K., Tarasov, S

    Kozlov, M. K., Tarasov, S. P., and Khachiyan, L. G. Polynomial solvability of convex quadratic programming. In Doklady Akademii Nauk, volume 248, pp.\ 1049--1051. Russian Academy of Sciences, 1979

    1979

  27. [35]

    Lenstra, H. W. and Jr. Integer programming with a fixed number of variables. Math. Oper. Res., 8 0 (4): 0 538--548, 1983

    1983

  28. [36]

    Bounds for the computational power and learning complexity of analog neural nets

    Maass, W. Bounds for the computational power and learning complexity of analog neural nets. SIAM J. Comput. , 26 0 (3): 0 708--732, 1997. doi:10.1137/S0097539793256041. URL https://doi.org/10.1137/S0097539793256041

    1997 doi

  29. [37]

    On the complexity of polyhedral separability

    Megiddo, N. On the complexity of polyhedral separability. Discret. Comput. Geom., 3: 0 325--337, 1988. doi:10.1007/BF02187916. URL https://doi.org/10.1007/BF02187916

    1988 doi

  30. [38]

    and Szeider, S

    Ordyniak, S. and Szeider, S. Parameterized complexity results for exact bayesian network structure learning. J. Artif. Intell. Res., 46: 0 263--302, 2013. doi:10.1613/jair.3744. URL https://doi.org/10.1613/jair.3744

    2013 doi

  31. [39]

    Methods for quadratic programming: A survey

    Pang, J.-S. Methods for quadratic programming: A survey. Computers & Chemical Engineering, 7 0 (5): 0 583--594, 1983

    1983

  32. [40]

    Effect of activation functions on the training of overparametrized neural nets

    Panigrahi, A., Shetty, A., and Goyal, N. Effect of activation functions on the training of overparametrized neural nets. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020 . OpenReview.net, 2020. URL https://openrev...

    2020

  33. [41]

    and Seymour, P

    Robertson, N. and Seymour, P. D. Graph minors. i. excluding a forest. J. Comb. Theory, Ser. B , 35 0 (1): 0 39--61, 1983

    1983

  34. [42]

    Schaefer, T. J. The complexity of satisfiability problems. In Lipton, R. J., Burkhard, W. A., Savitch, W. J., Friedman, E. P., and Aho, A. V. (eds.), Proceedings of the 10th Annual ACM Symposium on Theory of Computing, May 1-3, 1978, San Diego, California, USA , pp.\ 216--226....

    1978

  35. [43]

    V., Golovach, P

    Simonov, K., Fomin, F. V., Golovach, P. A., and Panolan, F. Refined complexity of PCA with outliers. In Chaudhuri, K. and Salakhutdinov, R. (eds.), Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA , vo...

    2019

  36. [44]

    A Decision Method for Elementary Algebra and Geometry: Prepared for Publication with the Assistance of J.C.C

    Tarski, A. A Decision Method for Elementary Algebra and Geometry: Prepared for Publication with the Assistance of J.C.C. McKinsey. RAND Corporation, Santa Monica, CA, 1951

    1951

  37. [45]

    benefits of depth in neural networks

    Telgarsky, M. benefits of depth in neural networks. In Feldman, V., Rakhlin, A., and Shamir, O. (eds.), Proceedings of the 29th Conference on Learning Theory, COLT 2016, New York, USA, June 23-26, 2016 , volume 49 of JMLR Workshop and Conference Proceedings , pp.\ 1517--1539. ...

    2016

  38. [46]

    and Reinsel, G

    Velu, R. and Reinsel, G. C. Multivariate reduced-rank regression: theory and applications, volume 136. Springer Science & Business Media, 2013

    2013

Pith tools

Reviewed August 1, 2026 · model on record in the stance chip above.