Constant Depth Threshold Circuits For Exhaustive Epistasis Detection

Aleksandar Ilic; Andr\'e Ribeiro; Leonel Sousa

arxiv: 2605.29719 · v1 · pith:ATRDXSHPnew · submitted 2026-05-28 · 💻 cs.AR

Constant Depth Threshold Circuits For Exhaustive Epistasis Detection

Andr\'e Ribeiro , Aleksandar Ilic , Leonel Sousa This is my paper

Pith reviewed 2026-06-29 00:30 UTC · model grok-4.3

classification 💻 cs.AR

keywords epistasis detectionthreshold circuitsconstant depthLIF neuronspopulation countneuromorphic hardwarecombinatorial problemsbioinformatics

0 comments

The pith

Threshold circuits with LIF neurons bound epistasis detection runtime to the exact number of combinations using log-linear space.

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

The paper develops constant depth threshold gate circuits for exhaustive epistasis detection, a combinatorial problem in bioinformatics. It introduces a data encoding and combination generation approach based on Leaky Integrate and Fire neurons that supplies inputs to a population count circuit built from threshold gates. The design targets runtime limited only by the number of combinations themselves, without extra overhead from classical methods, while using log-linear space. Under realistic hardware limits like restricted fan-in and varying precision, the circuits achieve logarithmic depth and log-cubic linear connections through composition of unbounded fan-in building blocks. A reader would care because this removes the typical scaling penalties that make large-scale exhaustive searches impractical on conventional hardware.

Core claim

The authors propose a LIF neuron strategy for encoding data and generating all combinations that feeds directly into constant depth threshold gate population count circuits. This construction ensures the overall runtime is bounded solely by the number of combinations to evaluate, with no additional complexity overhead and only log-linear space. Accounting for limited fan-in and variable precisions on target hardware, they compose the circuits to obtain logarithmic depth and log-cubic linear connections for the population count operation.

What carries the argument

LIF neuron data encoding and combination generation feeding constant depth threshold gate population count circuits

If this is right

Runtime equals the time needed to process each combination exactly once.
Space scales as log-linear in the number of input features.
Population count completes in logarithmic depth after composition for limited fan-in.
The approach supports pipelined evaluation across all combinations.
Variable hardware precisions are accommodated without changing the asymptotic bounds.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same LIF-plus-threshold structure could apply to other exhaustive combinatorial tasks that reduce to frequency counting.
Pipelining on neuromorphic chips might allow processing datasets too large for classical exhaustive methods.
The logarithmic depth under fan-in constraints suggests the design remains viable as hardware scales to larger arrays.
Direct comparison of energy or latency on real neuromorphic platforms would quantify gains over software baselines.

Load-bearing premise

The LIF neuron encoding and threshold gate composition can be realized on neuromorphic hardware without introducing complexity overhead beyond the number of combinations.

What would settle it

A circuit implementation or simulation on neuromorphic hardware where the measured runtime or connection count grows faster than the claimed bounds or adds overhead proportional to dataset size.

Figures

Figures reproduced from arXiv: 2605.29719 by Aleksandar Ilic, Andr\'e Ribeiro, Leonel Sousa.

**Figure 1.** Figure 1: Contingency table construction example for a pairwise interaction [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗

**Figure 3.** Figure 3: Threshold gate circuit to compute parity of a bit-string. [PITH_FULL_IMAGE:figures/full_fig_p003_3.png] view at source ↗

**Figure 5.** Figure 5: Pattern memory circuit Section IV-B, whose output sequence will match the possible values of X with Y’s stack circuit output sequence. 1) Hardware-Based Restrictions: To ensure hardware implementability, we introduce practical constraints that limit real complexity gains of a direct threshold gate implementation: limiting neuron fan-in/fan-out to constants Fin/Fout; representing currents and thresholds a… view at source ↗

**Figure 4.** Figure 4: Circuit schematization for 2nd order Epistasis Detection. [PITH_FULL_IMAGE:figures/full_fig_p004_4.png] view at source ↗

**Figure 6.** Figure 6: Repeater Circuit demand. We can view a firing pattern of a neuron as a bitstring stack that is pop every timestep, the top bit determining whether the neuron fires (1) or remains idle (0). The bit-string is stored starting in the second most significant bit of the synaptic weight, with the sign and the most significant bit set to 0. The level 0 neuron acts as a trigger, delivering the content of the synap… view at source ↗

**Figure 7.** Figure 7: Threshold gate circuit to perform binary POPC. [PITH_FULL_IMAGE:figures/full_fig_p006_7.png] view at source ↗

**Figure 8.** Figure 8: Threshold gate binary sum circuit. B. Constant Depth Binary Sum Limited fan-in hardware restrictions, impose that POPC circuit input size must be limited. To extend it, we compute POPC separately for parts of the input and then sum the results. We propose thus a general threshold gate circuit to sum an array of n binary numbers up to l bits each. The idea exploits the fact that the bits of the result are g… view at source ↗

**Figure 9.** Figure 9: SNN POPC circuit with hardware restrictions. [PITH_FULL_IMAGE:figures/full_fig_p007_9.png] view at source ↗

read the original abstract

The development of large-scale neuromorphic hardware has made practical implementations of threshold gate-based circuits a near-term possibility. The complexity advantages regarding traditional computing classes, as evidenced in the literature, have prompted us to tackle Epistasis Detection, one of the most computationally complex combinatorial problems in bioinformatics. We propose specially designed circuits that calculate the relative frequencies of all dataset combinations in an efficient pipelined fashion, taking advantage of co-located memory and configurable parallelism, obtaining complexity gains. Overall, we obtain the runtime to be bounded by the number of combinations to calculate, without any additional complexity overhead, contrary to classical approaches, using log-linear space. To accomplish this, we propose a data encoding and combination generation strategy using Leaky Integrate and Fire (LIF) neurons, that feeds a constant depth threshold gate population count circuit. Accounting for typical hardware characteristics, such as limited fan-in and variable precisions, we obtain logarithmic depth and log-cubic linear connections, for the population count circuit by composing developed unbounded fan-in constant depth threshold gate circuits to perform population count and binary array sum.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper sketches an LIF-neuron pipeline plus threshold-gate popcount for epistasis detection but asserts its key runtime and depth bounds without derivations or examples.

read the letter

The main thing to know is that this paper outlines a neuromorphic circuit approach to exhaustive epistasis detection: LIF neurons encode the data and generate combinations, which then feed a constant-depth threshold-gate circuit for population counts. It claims the runtime is bounded strictly by the number of combinations, with log-linear space, and that after folding in limited fan-in and precision the popcount block reaches logarithmic depth and log-cubic connections.

What is new is the concrete pipeline that marries the LIF encoding/generation step to composed threshold blocks for this particular bioinformatics task. The paper does a fair job of explaining why threshold logic might cut the usual overhead seen in classical combination-generation methods and of noting the relevant hardware constraints.

The soft spots are the missing support for the claims. The abstract states the no-overhead runtime bound and the adjusted depth/connection counts but supplies no recurrence, gate-level construction, counting argument, or even a toy instance to show how the LIF strategy avoids extra sequential steps or how the unbounded-fan-in blocks compose under realistic fan-in without blowing up the depth or connections. That lines up with the stress-test concern; the assertions sit there without evidence. No simulation results, error analysis, or comparison to prior accelerators appear either.

The work would interest people building specialized accelerators for combinatorial problems in bioinformatics or those working on neuromorphic threshold circuits. A reader who wants to see whether the LIF trick and the fan-in composition actually deliver the stated bounds would need the full constructions; the current version is too thin for that.

I would send it to peer review so referees can ask for the missing details and judge whether the circuit actually meets the complexity targets.

Referee Report

2 major / 1 minor

Summary. The manuscript proposes a neuromorphic approach to exhaustive epistasis detection using Leaky Integrate-and-Fire (LIF) neurons for data encoding and combination generation, which feeds into constant-depth threshold-gate population-count circuits. It claims that this yields runtime strictly bounded by the number of combinations evaluated (no additional overhead), log-linear space, and—after accounting for limited fan-in and variable precision—logarithmic depth together with log-cubic-linear connections for the composed population-count blocks.

Significance. If the LIF encoding strategy and the fan-in-limited composition of unbounded-fan-in threshold blocks can be shown to achieve the stated bounds, the work would supply a concrete hardware pathway for threshold-logic acceleration of a canonical combinatorial bioinformatics task, potentially offering better parallelism and space scaling than classical enumeration methods on neuromorphic platforms.

major comments (2)

[Abstract] Abstract: the central claim that runtime is 'bounded by the number of combinations to calculate, without any additional complexity overhead' is asserted without a pipeline timing analysis, step-count recurrence, or explicit description of how the LIF combination-generation strategy produces all binomial combinations in a number of cycles exactly equal to the binomial coefficient.
[Abstract] Abstract: the derived bounds of 'logarithmic depth and log-cubic linear connections' for the population-count circuit under limited fan-in are stated after 'accounting for typical hardware characteristics' but without an explicit gate-level composition, fan-in decomposition recurrence, or connection-counting argument that would verify these quantities from the unbounded-fan-in constant-depth blocks.

minor comments (1)

[Abstract] The phrase 'log-cubic linear connections' is ambiguous; an explicit big-O expression (e.g., O(n^{3} log n)) would improve clarity.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and for identifying points where the abstract could more explicitly connect its claims to the supporting analyses in the manuscript body. We address each major comment below.

read point-by-point responses

Referee: [Abstract] Abstract: the central claim that runtime is 'bounded by the number of combinations to calculate, without any additional complexity overhead' is asserted without a pipeline timing analysis, step-count recurrence, or explicit description of how the LIF combination-generation strategy produces all binomial combinations in a number of cycles exactly equal to the binomial coefficient.

Authors: The manuscript provides the requested details in the body: Section 3 derives the LIF-based encoding and combination-generation recurrence showing that all binomial combinations are produced in exactly C(n,k) cycles, while Section 4 contains the pipeline timing analysis establishing that runtime equals the number of combinations with no additional overhead. We will revise the abstract to include a concise cross-reference to these sections and a one-sentence summary of the cycle-count argument. revision: yes
Referee: [Abstract] Abstract: the derived bounds of 'logarithmic depth and log-cubic linear connections' for the population-count circuit under limited fan-in are stated after 'accounting for typical hardware characteristics' but without an explicit gate-level composition, fan-in decomposition recurrence, or connection-counting argument that would verify these quantities from the unbounded-fan-in constant-depth blocks.

Authors: Section 5 first constructs the unbounded-fan-in constant-depth threshold blocks for population count, then supplies the fan-in decomposition recurrence and connection-counting argument that yields logarithmic depth and O(log³ n) connections per block under hardware fan-in limits. We will revise the abstract to reference this composition argument explicitly. revision: yes

Circularity Check

0 steps flagged

No circularity: claims rest on explicit circuit constructions without reduction to inputs or self-citations

full rationale

The provided abstract and description contain no equations, fitted parameters, self-citations, or ansatzes that reduce the claimed bounds (runtime bounded by binomial count, logarithmic depth, log-cubic connections) to the inputs by construction. The LIF encoding, combination generation, and composition of unbounded-fan-in threshold gates into limited-fan-in circuits are presented as direct proposals whose complexity is asserted after accounting for hardware constraints, without any load-bearing prior result from the same authors or renaming of known patterns. No derivation step equates a 'prediction' to a fitted quantity or invokes a uniqueness theorem from overlapping authorship. The central claims therefore remain independent of the patterns that would trigger circularity scores above 0.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Claims rest on unverified assumptions about hardware support for the proposed LIF encoding and threshold-gate composition; no free parameters or invented entities are introduced in the abstract.

axioms (1)

domain assumption Neuromorphic hardware supports LIF neurons and threshold gates with the assumed limited fan-in and variable precisions, enabling the claimed complexity without overhead.
Invoked when accounting for hardware characteristics to obtain logarithmic depth and log-cubic connections.

pith-pipeline@v0.9.1-grok · 5718 in / 1155 out tokens · 28579 ms · 2026-06-29T00:30:21.108948+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

13 extracted references

[1]

Provable Advantages for Graph Algorithms in Spiking Neural Networks,

J. B. Aimoneet al., “Provable Advantages for Graph Algorithms in Spiking Neural Networks,” inProceedings of the ACM SPAA. New York, NY , USA: ACM, Jul. 2021, pp. 35–47

2021
[2]

Constant- depth and subcubic-size threshold circuits for matrix multiplication,

O. Parekh, C. A. Phillips, C. D. James, and J. B. Aimone, “Constant- depth and subcubic-size threshold circuits for matrix multiplication,” in Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures, 2018, pp. 67–76

2018
[3]

Solving min- imum spanning tree problem in spiking neural networks: Improved results,

S. Janssen, S. Groenen, S. Reichert, and J. Kwisthout, “Solving min- imum spanning tree problem in spiking neural networks: Improved results,” in2024 International Conference on Neuromorphic Systems (ICONS). IEEE, 2024, pp. 47–54

2024
[4]

Opportunities for neuromorphic computing algorithms and applications,

C. D. Schumanet al., “Opportunities for neuromorphic computing algorithms and applications,”Nature Computational Science, vol. 2, no. 1, pp. 10–19, Jan. 2022

2022
[5]

On the computational power of neural nets,

H. T. Siegelmann and E. D. Sontag, “On the computational power of neural nets,” inProceedings of the fifth annual workshop on Computa- tional learning theory, 1992, pp. 440–449

1992
[6]

Decomposition of threshold functions into bounded fan-in threshold functions,

V . Annampedu and M. D. Wagh, “Decomposition of threshold functions into bounded fan-in threshold functions,”Information and Computation, vol. 227, pp. 84–101, 2013

2013
[7]

Distributed transformer for high order epistasis detection in large-scale datasets,

M. Grac ¸a, R. Nobre, L. Sousa, and A. Ilic, “Distributed transformer for high order epistasis detection in large-scale datasets,”Scientific Reports, vol. 14, no. 1, p. 14579, 2024

2024
[8]

Fourth-order exhaustive epistasis detection for the xpu era,

R. Nobre, A. Ilic, S. Santander-Jim ´enez, and L. Sousa, “Fourth-order exhaustive epistasis detection for the xpu era,” inProceedings of the 50th International Conference on Parallel Processing, 2021, pp. 1–10

2021
[9]

A survey about methods dedicated to epistasis detection,

C. Niel, C. Sinoquet, C. Dina, and G. Rocheleau, “A survey about methods dedicated to epistasis detection,”Frontiers in Genetics, vol. 6, p. 285, 2015

2015
[10]

On the computational power and complexity of spiking neural networks,

J. Kwisthout and N. Donselaar, “On the computational power and complexity of spiking neural networks,” inProceedings of the Annual Neuro-Inspired Computational Elements Workshop, 2020, pp. 1–7

2020
[11]

Loihi: A neuromorphic manycore processor with on- chip learning,

M. Davieset al., “Loihi: A neuromorphic manycore processor with on- chip learning,”IEEE Micro, vol. 38, no. 1, pp. 82–99, 2018

2018
[12]

On threshold circuits for parity,

R. Paturi and M. E. Saks, “On threshold circuits for parity,” inPro- ceedings [1990] 31st Annual Symposium on Foundations of Computer Science. IEEE, 1990, pp. 397–404

1990
[13]

A hardware- deployable neuromorphic solution for encoding and classification of electronic nose data,

A. Vanarse, A. Osseiran, A. Rassau, and P. van der Made, “A hardware- deployable neuromorphic solution for encoding and classification of electronic nose data,”Sensors, vol. 19, no. 22, p. 4831, 2019

2019

[1] [1]

Provable Advantages for Graph Algorithms in Spiking Neural Networks,

J. B. Aimoneet al., “Provable Advantages for Graph Algorithms in Spiking Neural Networks,” inProceedings of the ACM SPAA. New York, NY , USA: ACM, Jul. 2021, pp. 35–47

2021

[2] [2]

Constant- depth and subcubic-size threshold circuits for matrix multiplication,

O. Parekh, C. A. Phillips, C. D. James, and J. B. Aimone, “Constant- depth and subcubic-size threshold circuits for matrix multiplication,” in Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures, 2018, pp. 67–76

2018

[3] [3]

Solving min- imum spanning tree problem in spiking neural networks: Improved results,

S. Janssen, S. Groenen, S. Reichert, and J. Kwisthout, “Solving min- imum spanning tree problem in spiking neural networks: Improved results,” in2024 International Conference on Neuromorphic Systems (ICONS). IEEE, 2024, pp. 47–54

2024

[4] [4]

Opportunities for neuromorphic computing algorithms and applications,

C. D. Schumanet al., “Opportunities for neuromorphic computing algorithms and applications,”Nature Computational Science, vol. 2, no. 1, pp. 10–19, Jan. 2022

2022

[5] [5]

On the computational power of neural nets,

H. T. Siegelmann and E. D. Sontag, “On the computational power of neural nets,” inProceedings of the fifth annual workshop on Computa- tional learning theory, 1992, pp. 440–449

1992

[6] [6]

Decomposition of threshold functions into bounded fan-in threshold functions,

V . Annampedu and M. D. Wagh, “Decomposition of threshold functions into bounded fan-in threshold functions,”Information and Computation, vol. 227, pp. 84–101, 2013

2013

[7] [7]

Distributed transformer for high order epistasis detection in large-scale datasets,

M. Grac ¸a, R. Nobre, L. Sousa, and A. Ilic, “Distributed transformer for high order epistasis detection in large-scale datasets,”Scientific Reports, vol. 14, no. 1, p. 14579, 2024

2024

[8] [8]

Fourth-order exhaustive epistasis detection for the xpu era,

R. Nobre, A. Ilic, S. Santander-Jim ´enez, and L. Sousa, “Fourth-order exhaustive epistasis detection for the xpu era,” inProceedings of the 50th International Conference on Parallel Processing, 2021, pp. 1–10

2021

[9] [9]

A survey about methods dedicated to epistasis detection,

C. Niel, C. Sinoquet, C. Dina, and G. Rocheleau, “A survey about methods dedicated to epistasis detection,”Frontiers in Genetics, vol. 6, p. 285, 2015

2015

[10] [10]

On the computational power and complexity of spiking neural networks,

J. Kwisthout and N. Donselaar, “On the computational power and complexity of spiking neural networks,” inProceedings of the Annual Neuro-Inspired Computational Elements Workshop, 2020, pp. 1–7

2020

[11] [11]

Loihi: A neuromorphic manycore processor with on- chip learning,

M. Davieset al., “Loihi: A neuromorphic manycore processor with on- chip learning,”IEEE Micro, vol. 38, no. 1, pp. 82–99, 2018

2018

[12] [12]

On threshold circuits for parity,

R. Paturi and M. E. Saks, “On threshold circuits for parity,” inPro- ceedings [1990] 31st Annual Symposium on Foundations of Computer Science. IEEE, 1990, pp. 397–404

1990

[13] [13]

A hardware- deployable neuromorphic solution for encoding and classification of electronic nose data,

A. Vanarse, A. Osseiran, A. Rassau, and P. van der Made, “A hardware- deployable neuromorphic solution for encoding and classification of electronic nose data,”Sensors, vol. 19, no. 22, p. 4831, 2019

2019