Sparse Parity Challenge

Can you solve sparse parity with less energy than a neural network?

Given random {-1, +1} inputs and a label that's the product of k secret bits, find those bits. The catch: we measure not just accuracy and speed, but data movement -- how much energy your solution costs at the hardware level.

Submit a Solution

Paste a Python function, pick a config, submit. GitHub Actions runs it automatically and posts your results.

Function signature

def solve(x, y, n_bits, k_sparse):
    """
    Args:
        x: numpy array (n_samples, n_bits), values in {-1, +1}
        y: numpy array (n_samples,), values in {-1, +1}
        n_bits: int, total number of bits
        k_sparse: int, number of secret bits
    Returns:
        list[int]: sorted indices of the k secret bits
    """

Rules

• Only numpy allowed (imported as np)
• No file I/O, network, or dynamic execution
• 60 second timeout
• Must achieve ≥95% accuracy across 3 seeds
• Evaluated with TrackedArray for automatic DMD measurement

Submitting via CLI

Adding labels requires collaborator access. If you're not a collaborator, use the web form above -- it auto-applies the label and works for everyone.

# Collaborators only: create issue + add label
gh issue create --repo cybertronai/sparse-parity-challenge \
  --title "Submission: your_method_name" \
  --body "$(cat your_solution.py)"
gh issue edit <number> --repo cybertronai/sparse-parity-challenge --add-label submission

Leaderboard

Ranked by DMD (Data Movement Distance) -- lower is better.

Rank	Method	Author	DMC	Time	Accuracy	Issue
1	Sequential Elimination	@Hydral8	19,153	0.0085s	100%	#30
2	passive_gf2_rref_minimal_22rows	@Hydral8	45,904	0.0002s	100%	#24
3	GF(2) Ultra-Minimal (n+1 samples, retry)	@SethTS	286,011	0.0044s	100%	#19
4	GF(2) Minimal (2n samples)	@SethTS	601,157	0.0087s	100%	#17
5	SMT Backtracking (n+1 samples) (v1)	@0bserver07	1,625,260	0.0063s	100%	#33
6	GF(2) Gaussian Elimination	@SethTS	11,164,685	0.1011s	100%	#13
7	new solution coded live during the Friday Rochester seminar.	@yaroslavvb	14,748,439	0.1075s	100%	#37
8	new gf2 proposed candidate	@yaroslavvb	24,397,704	0.0019s	100%	#22

The metric

Current evaluation: TrackedArray (element-level, numpy-aware). Your numpy operations get automatically tracked. DMD = sum of sqrt(stack_distance) per element read. Lower = better.

New (in transition): ByteDMD -- byte-granularity, pure Python, deterministic. Vendored at src/bytedmd/. Reads cost ceil(sqrt(depth)) per byte, writes are free. Tests in tests/test_bytedmd.py.

The transition is in progress. Existing leaderboard entries are measured with the legacy TrackedArray metric. New submissions can be evaluated under both metrics once bin/evaluate is updated. See cybertronai/ByteDMD for the spec.

The neural network baseline (SGD) has DMD ~1.3M under TrackedArray. The best known solution (KM influence estimation) has DMD ~3,600. Can you beat it?

Research context

This challenge comes from the Sutro Group, a study group at South Park Commons exploring energy-efficient AI training. 36 experiments across algebraic, information-theoretic, and neural approaches. The full research is at cybertronai/SutroYaro.

Local testing

git clone https://github.com/cybertronai/sparse-parity-challenge.git
cd sparse-parity-challenge
pip install numpy

# Test your solve() function locally
PYTHONPATH=src python3 -c "
import numpy as np
from sparse_parity.tracked_numpy import TrackedArray, tracking_context
from sparse_parity.lru_tracker import LRUStackTracker

# Your function here
def solve(x, y, n_bits, k_sparse):
    # example: GF(2) or whatever you want to try
    pass

# Generate data
rng = np.random.RandomState(42)
n_bits, k_sparse = 20, 3
secret = sorted(rng.choice(n_bits, k_sparse, replace=False).tolist())
x = rng.choice([-1.0, 1.0], size=(500, n_bits))
y = np.prod(x[:, secret], axis=1)

# Evaluate with tracking
tracker = LRUStackTracker()
with tracking_context(tracker):
    x_t = TrackedArray(x, 'x', tracker)
    y_t = TrackedArray(y, 'y', tracker)
    result = solve(x_t, y_t, n_bits, k_sparse)

print(f'Found: {result}')
print(f'Secret: {secret}')
print(f'Correct: {sorted(result) == secret}')
print(f'DMD: {tracker.summary()[\"dmd\"]:,.1f}')
"