Pith. sign in

REVIEW 4 major objections 9 minor 12 references

Learning Nonlinearity of Boolean Functions: An Experimentation with Neural Networks

T0 review · 4 major / 9 minor · reviewed 2026-08-09 · deepseek-v4-flash

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

Pith's one-line read Deep encoder networks predict Boolean-function nonlinearity above 95 percent for 4 and 5 variables.

desk verdict A small, honest empirical study: deep nets can predict Boolean-function nonlinearity for n=4,5, but the headline accuracy numbers need a fully specified evaluation protocol before they can be fully trusted. read the letter →

arxiv 2502.01060 v1 pith:BQWZ6XCY submitted 2025-02-03 cs.LG cs.AIcs.CR

Sriram Ranga , Nandish Chattopadhyay , Anupam Chattopadhyay This is my paper · ORCID
classification cs.LGcs.AIcs.CR MSC 06E3068T0794A60
keywords BooleanfunctionsnonlinearityWalshspectrumWalsh-Hadamardtransformneuralnetworklearningcryptographicpropertiesdeep
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

The paper asks whether a neural network can learn a deterministic property of Boolean functions—nonlinearity, the minimum Hamming distance from all affine functions—from examples alone, without being told the Walsh-spectrum calculation. It reports that wide encoder-style fully connected networks, fed only truth tables and nonlinearity values, reach about 99.5 percent test accuracy for 4-variable functions and 96.2 percent for 5-variable functions. A single-layer linear network can also learn the Walsh transform itself, with its trained weight matrix converging to the Walsh-Hadamard matrix. The authors are explicit that the approach could not be extended to six or more variables in their experiments, and that the trained networks are neither faster nor more compact than the standard Fast Walsh Transform. The positive claim is therefore carefully bounded: nonlinearity is learnable end-to-end for small variable counts, but no practical advantage over deterministic algorithms is established.

What carries the argument

The load-bearing identity is nonlinearity as a function of the Walsh spectrum: for an n-variable Boolean function, $nl(f) = 2^{n-1} - \frac{1}{2} \max_{\omega} |W_f(\omega)|$, where $W_f$ is the Walsh transform, meaning the inner products of the function's $\pm 1$ truth table with all linear characters. This turns nonlinearity into a linear or affine transformation followed by a max operation, which the paper uses in two ways: a single linear layer should learn the Walsh-Hadamard matrix, and a deeper encoder with ReLU activations and a final single neuron is asked to learn the full composition end-to-end. The encoder architectures, 64 to 1 neurons for n=4 and 512 to 1 for n=5, are the mechanism that succeeds where the shallow min-and-max-pool network fails.

What would settle it

Train the same architecture and evaluate it on a test set stratified so each true nonlinearity value appears equally often; if overall accuracy drops far below the reported 95 percent, the original result was an artifact of the natural class imbalance rather than learned nonlinearity.

Watch

Extended reading notes

Core claim

The central discovery is that end-to-end nonlinearity prediction, a deterministic computation involving an affine transformation followed by finding a maximum absolute Walsh coefficient, can be reproduced by a deep encoder network from truth-table and nonlinearity pairs for n=4 and n=5, even though a shallow network with a max-pool layer that logically models the computation fails to converge during training. For the Walsh-spectrum sub-problem, a single linear layer with N outputs learns the correct Walsh-Hadamard transform, and N linearly independent example functions suffice for convergence. For the full property, the paper reports 99.7 percent train and 99.5 percent test accuracy on 4 variables with about half the function space as training data, and 98.2 percent train and 96.2 percent test accuracy on 5 variables with much larger data and model; attempts at six variables failed. The authors read these results as evidence that the property is learnable in small dimensions, but that model and data requirements grow so rapidly that the neural approach does not beat classical algorithms.

Load-bearing premise

The load-bearing assumption is that test accuracy measured on randomly held-out Boolean functions of 4 and 5 variables reliably measures genuine generalization; if the split, network size, seed, or output decoding were chosen differently, the reported 95 percent figures could change.

Editorial extensions

If this is right

  • A neural network trained on a random sample of Boolean functions can generalize to held-out functions in 4 and 5 variables with high accuracy, so end-to-end learning of this cryptographic property is possible in principle.
  • The single-layer Walsh-spectrum result shows that the learned weights coincide with the Walsh-Hadamard matrix, and that N linearly independent truth tables are sufficient to identify it, matching the sample count needed to solve the linear system explicitly.
  • The shallow architecture that mirrors the exact nonlinearity computation does not converge under gradient descent, suggesting that representational adequacy alone does not make the task learnable.
  • Scaling from 4 to 5 variables required roughly a 50-fold increase in parameters and a 6-fold increase in examples, and six variables did not train; therefore resource growth is steep for this task.
  • Because inference through the trained network is slower and heavier than a Fast Walsh Transform, the paper finds no time or memory advantage for the neural approach.

Reading between the lines

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

  • The failure of the shallow logic-matching network and the success of the deeper encoder suggest the loss landscape, not expressivity, is the barrier; a natural test is whether symmetry-breaking architectures, for example permutation-equivariant pooling over the affine rows, recover convergence with far fewer parameters.
  • The reported accuracy is aggregated over all nonlinearity values, and for n=5 those values are strongly imbalanced; a reader should check per-class accuracy on rare high-nonlinearity functions before treating the model as a true estimator rather than a majority-class predictor.
  • The exact Walsh-spectrum learning result could be repurposed as a warm start or curriculum for end-to-end training, since the max operation is the only non-linear component separating the two tasks.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

4 major / 9 minor

Summary. The paper studies whether neural networks can learn to compute the nonlinearity of Boolean functions from truth-table examples. In a first experiment, a single linear layer is trained to map {−1,1}-encoded truth tables to Walsh spectra, and the learned weight matrix is reported to resemble the Walsh–Hadamard matrix; the authors support this with a linear-algebra argument that N = 2^n linearly independent training functions determine the transformation matrix uniquely. In a second experiment, encoder-style ReLU networks are trained end-to-end to predict the nonlinearity value directly from the truth table, with reported test accuracies of 99.5% for n = 4 and 96.2% for n = 5, and failure to scale to n ≥ 6. The paper concludes that nonlinearity is learnable for small numbers of variables but that the trained networks are not competitive with the fast Walsh transform in time or memory.

Significance. If the empirical claims are reproducible, the paper would provide a useful data point: a discrete, deterministic cryptographic property can be predicted by gradient-trained networks on small variable counts, and the Walsh-spectrum stage yields an interpretable solution. The Walsh-spectrum result is well supported: the linear algebra argument in Section 3.1 is sound, and the experimental observation of the Hadamard matrix is plausible. However, the end-to-end claim rests on a single, underspecified experimental protocol, so the significance of the headline >95% accuracy is currently not established. The paper also honestly acknowledges the lack of scaling and efficiency gains, which is a strength, but the missing baselines, error bars, and protocol details prevent the reader from distinguishing learning from a favorable evaluation setup.

major comments (4)
  1. [Section 3.2, Table 1, Fig. 4] The headline accuracies (99.5% for n = 4 and 96.2% for n = 5) are not reproducible because the paper does not state the loss function, the rule for mapping the single real-valued output neuron to a discrete nonlinearity value (rounding, tolerance, or class argmax), the train/test split sizes, or the sampling procedure. An exact-match-after-rounding metric and a tolerance-based metric are different claims, and the reported numbers could shift under either decoding.
  2. [Section 3.2, n = 4 experiment] With 2^16 = 65,536 possible 4-variable functions and a training set of 'around half the function space (30k examples)', the paper does not state whether the test set was the complement of the training set or sampled independently. If a test set of comparable size (~30,000) were sampled independently from the full function space, the expected number of train/test overlaps would be about 30,000^2 / 65,536 ≈ 13,700, which would inflate test accuracy because overlapping examples were already seen during training. The split strategy must be reported and overlap must be excluded.
  3. [Section 3.2] No baseline or control is reported. To support the claim that deep neural networks 'are able to learn to predict the property', the results should be compared with non-neural baselines under the same protocol, such as a k-nearest-neighbor predictor on truth tables, a gradient-boosted tree, or a simple handcrafted feature-based estimator. Without such comparisons, the observed performance cannot be attributed to the network architecture rather than to the structure of the dataset or the ease of the prediction task.
  4. [Section 3.2 and Table 1] The training configuration is not specified: optimizer, learning rate, batch size, number of epochs, weight initialization, regularization, and the convergence criterion are omitted. The statement that the first-layer width was 'decided by trial and error' is not a reproducible procedure, and the sensitivity of the reported accuracies to these choices is unknown. The n = 5 result in particular is a single number with no confidence interval, and the test set size for n = 5 is not given.
minor comments (9)
  1. [Section 3.1, Eq. (15)] The learned weight matrix is displayed rounded to three decimals; please report the maximum absolute deviation from the exact Hadamard matrix and state whether this agreement held uniformly for all n = 2 through 10 or only for the n = 2 example shown.
  2. [Table 1] The parameter count for the n = 5 network appears inconsistent with the stated layer widths: summing (32×512+512) + (512×256+256) + ... + (2×1+1) gives 192,169 parameters, not the reported 192,196. Please verify the arithmetic and correct the table.
  3. [Section 3.2, n = 3 case] The failure for 3-variable functions is attributed to the small size of the function space (256 functions), but an optimization failure on the chosen architecture is also plausible; reporting the training set size, loss trajectories, and a sweep over initializations would clarify the cause.
  4. [Eq. (13)] The composition notation with σ(k−1) is confusing because the output layer's activation is not defined; please define the activation structure of each layer explicitly, including whether the final layer is linear.
  5. [Introduction and Section 1.1] Several inline expressions render '2n' where '2^n' is meant, e.g., 'minimum of 2 n functions' in Section 1.1; please typeset exponents consistently throughout the manuscript.
  6. [References] Reference [1] is given in a garbled form ('David, D., Richard, J.'); the Deutsch–Jozsa paper should be cited with the correct authors. Reference [10] also lacks complete publication details.
  7. [Fig. 2] The plot showing accuracy versus the number of training functions should include the number of runs and error bars; with a single seed, the qualitative drop shown may not be stable.
  8. [Section 3.2] The phrase 'statutory warning' is unusual in a scientific context; consider replacing it with a more standard formulation such as 'we caution that'.
  9. [Section 3.2] The code is said to be available on GitHub, but no repository URL is provided; please include a link and, if possible, a configuration file with all hyperparameters.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity detected: the targets are computed by independent Walsh-transform formulas, and no self-citation chain or fitted-parameter prediction is present.

full rationale

The paper's central claims are supervised-learning results against independently computed targets. For the Walsh-spectrum experiment, the network is trained on pairs of processed truth tables and Walsh spectra computed by Eq. 12; the learned weight matrix is then compared to the known Walsh-Hadamard matrix as an external benchmark. The fact that a linear layer can recover the Hadamard matrix from enough linearly independent examples is a standard linear-regression result, not a prediction that is defined in terms of the network's own outputs. For the end-to-end nonlinearity experiment, the target nonlinearity values are computed from the Walsh spectrum via Eq. 9, which is a deterministic formula independent of the trained encoder network. There are no fitted parameters that are renamed as predictions, no load-bearing self-citations, and no imported uniqueness theorems. The paper's omissions concerning train/test split details, output decoding, and multiple-seed variance are correctness and reproducibility concerns, not circularity concerns, because they do not show that the reported accuracy is equivalent to the training input by construction.

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

The central claim is empirical, so it rests on the training data and network choices rather than on invented entities or free parameters in a theoretical derivation. The listed free parameters are the manual choices (architecture, training set size, optimizer settings) that the reported accuracy depends on. The axioms are standard mathematical facts plus implicit assumptions about the experimental protocol.

free parameters (4)
  • Base width of first hidden layer = 64 for n=4, 512 for n=5
    Chosen by trial and error (Section 3.2); the network architecture and hence the predictions depend on this choice.
  • Number of hidden layers = 7 for n=4, 10 for n=5
    Chosen by trial and error; adding or removing layers changed accuracy dramatically (Section 3.2).
  • Number of training examples = 30,000 for n=4; 200,000 for n=5
    Selected to reach the reported accuracy; no scaling rule is given.
  • Optimization hyperparameters (learning rate, epochs, batch size) = not reported
    Not specified in the paper, so the reported results depend on undisclosed choices.
assumptions (5)
  • standard math The Walsh-Hadamard transform matrix H_N describes the Walsh spectrum via Eq. 12 and nonlinearity via Eq. 9.
    Used throughout Section 2 as background; standard results in Boolean function analysis.
  • standard math A linear system with N linearly independent equations has a unique solution for the N^2 unknowns of the transformation matrix.
    Invoked in Section 3.1 to argue N training functions suffice to determine the Hadamard matrix.
  • standard math Linear regression with a quadratic loss is convex, so gradient descent reaches a global minimum.
    Mentioned in Section 3.1 to support convergence of the single-layer Walsh-spectrum network.
  • domain assumption The train and test sets are sampled uniformly from the space of all n-variable Boolean functions and are independent.
    Assumed in Section 3.2 when reporting train/test accuracy as a measure of generalized learnability; the split procedure is not described.
  • domain assumption The network output (one neuron) can be decoded to a nonlinearity value, and the loss function is appropriate for the task.
    Not specified in the paper; the accuracy metric depends on this decoding, e.g., classification vs. regression with rounding.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Learning Nonlinearity of Boolean Functions: An Experimentation with Neural Networks." pith.science (2026). https://pith.science/paper/BQWZ6XCY

@misc{pith2026250201060,
  author       = {Pith},
  title        = {Pith review of: Learning Nonlinearity of Boolean Functions: An Experimentation with Neural Networks},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/BQWZ6XCY}},
  note         = {Machine review of arXiv:2502.01060}
}
read the original abstract

This paper investigates the learnability of the nonlinearity property of Boolean functions using neural networks. We train encoder style deep neural networks to learn to predict the nonlinearity of Boolean functions from examples of functions in the form of a truth table and their corresponding nonlinearity values. We report empirical results to show that deep neural networks are able to learn to predict the property for functions in 4 and 5 variables with an accuracy above 95%. While these results are positive and a disciplined analysis is being presented for the first time in this regard, we should also underline the statutory warning that it seems quite challenging to extend the idea to higher number of variables, and it is also not clear whether one can get advantage in terms of time and space complexity over the existing combinatorial algorithms.

Figures

Figures reproduced from arXiv: 2502.01060 by the authors.

Figure 1
Figure 1. Network used for learning the Walsh spectrum of n-variable Boolean functions. Processed Boolean functions (after replacing 0/1 in their truth tables with 1/-1) and corresponding Walsh spectra are used as examples to train the network. The weight matrix after convergence resembles the Walsh Hadamard matrix. For a general k layer feed-forward neural network, the output is given by f(x) = σ (k−1)(b (k−1) + W(k−1) σ (k−… view at source ↗
Figure 2
Figure 2. Accuracy of the model drops significantly when less than N linearly independent functions are given as inputs to the linear network. The drop gets sharper as n increases. It was observed that N linearly independent inputs were enough to train the network, but using a larger number of inputs helps the network to converge faster (Up to 100x speedup was observed for larger values of n). This approach has the advantages… view at source ↗
Figure 3
Figure 3. Networks used for learning the nonlinearity of Boolean functions in an end to end fashion. Only Boolean functions and corresponding nonlinearity values are used as examples to train the network. On the left is a network that can model nonlinearity calculation, but does not respond well to training. As an example, expected weights for 2-variable functions are given. On the right is the deep encoder style network usin… view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: Confusion matrices of the predictions made by the model trained on 4-variable Boolean functions in an end to end fashion. Predictions for train and test data are given. References 1. David, D., Richard, J.: Rapid solution of problems by quantum computation. Proceedings…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

12 extracted references · 11 canonical work pages

  1. [1]

    Proceedings of the Royal Society of London A 439, 553–558 (1992)

    David, D., Richard, J.: Rapid solution of problems by quantum computation. Proceedings of the Royal Society of London A 439, 553–558 (1992). DOI 10.1098/rspa.1992.0167

    work page arXiv 1992

  2. [2]

    Entropy 24(8), 1117 (2022)

    Erdal, M., Schwenker, F.: Learnability of the Boolean innerproduct in deep neural networks. Entropy 24(8), 1117 (2022). DOI 10.3390/e24081117

    work page doi:10.3390/e24081117 2022

  3. [3]

    IEEE Transactions on Computers p

    Fino, B., Algazi, V.: Unified matrix treatment of the fast Walsh-Hadamard trans- form. IEEE Transactions on Computers p. 1142–46 (1976). DOI 10.1109/TC.1976. 1674569

    work page doi:10.1109/tc.1976 1976

  4. [4]

    Mathematical systems theory 17, 13–27 (1981)

    Furst, M.L., Saxe, J.B., Sipser, M.: Parity, circuits, and the polynomial-time hierarchy. Mathematical systems theory 17, 13–27 (1981). URL https://api. semanticscholar.org/CorpusID:6306235

    work page 1981

  5. [5]

    Hillery, M., Andersson, E.: Quantum tests for the linearity and permutation invariance of Boolean functions. Phys. Rev. A 84, 062,329 (2011). DOI 10.1103/PhysRevA.84.062329

    work page doi:10.1103/physreva.84.062329 2011

  6. [6]

    Neural Networks 12(9), 1321–1323 (1999)

    Hohil, M.E., Liu, D., Smith, S.H.: Solving the n-bit parity problem using neural networks. Neural Networks 12(9), 1321–1323 (1999). DOI 10.1016/S0893-6080(99) 00069-6

    work page doi:10.1016/s0893-6080(99 1999

  7. [7]

    Mathematical Perspectives on Neural Networks (1996)

    Parberry, I.: Circuit complexity and feedforward neural networks. Mathematical Perspectives on Neural Networks (1996)

    work page 1996

  8. [8]

    Rivest, R.L.: Cryptography and machine learning. In: G. Goos, J. Hartmanis, H. Imai, R.L. Rivest, T. Matsumoto (eds.) Advances in Cryptology — ASI- ACRYPT ’91, vol. 739, pp. 427–439. Springer Berlin Heidelberg, Berlin, Heidelberg (1993). DOI 10.1007/3-540-57332-1 36

    work page doi:10.1007/3-540-57332-1 1993

Show all 12 references
  1. [9]

    Sarkar, P., Maitra, S.: Construction of nonlinear Boolean functions with important cryptographic properties. In: B. Preneel (ed.) Advances in Cryptology — EURO- CRYPT 2000, pp. 485–506. Springer Berlin Heidelberg, Berlin, Heidelberg (2000). DOI 10.1007/3-540-45539-6 35

    2000 doi

  2. [10]

    19–20 (2002)

    Steinbach, B., Kohut, R.: Neural networks - a model of Boolean functions pp. 19–20 (2002). URL https://www.researchgate.net/publication/246931125 Neural Networks - A Model of Boolean Functions Learning Nonlinearity of Boolean Functions 13

    2002

  3. [11]

    CoRR abs/2009.05908 (2020)

    Tavares, A.R., Avelar, P.H.C., Flach, J.M., Nicolau, M., Lamb, L.C., Vardi, M.Y.: Understanding Boolean function learnability on deep neural networks. CoRR abs/2009.05908 (2020)

    2020

  4. [12]

    Advances in Computer Science and Technology

    Wu, C.K., Feng, D.: Boolean functions and their applications in cryptography. Advances in Computer Science and Technology. Springer Berlin Heidelberg, Berlin, Heidelberg (2016). DOI 10.1007/978-3-662-48865-2

    2016 doi

Pith tools

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