Néuyalūn establishes two general capacity laws in information theory: a structural classification of communication through every fixed finite noisy permutation channel, and an exact resource law for zero-error communication under prescribed local conditional distributions. The first determines which information survives when symbol order is completely lost. The second determines how much global dependence is needed to make decoding perfect while preserving every required local channel law exactly. Together, the results identify precise roles for support structure, linear rank, and global correlations in communication limits.

Néuyalūn: A General Capacity Classification for Finite Noisy Permutation Channels and Exact Dependence Frontiers for Zero-Error Communication | Zenodo

PureOne/Neuyalun-General-Finite-Channel-Capacity · Datasets at Hugging Face

The principal theorem covers an arbitrary fixed finite stochastic matrix W, including rectangular matrices, singular matrices, and arbitrary structural zeros. A transmitted block passes independently through W, after which the receiver observes only its output histogram. Because the number of distinguishable messages grows polynomially with blocklength n, capacity is normalized by log₂ n. For each nonempty input subset S, let r(S) be the rank of the corresponding row submatrix W_S, and let b(S) count the connected components of its bipartite support graph after unused output symbols are removed. The exact capacity coefficient is:

C_perm(W) = γ(W) = max_{nonempty S} [r(S) + b(S) − 2]/2.

This formula supplies a finite characterization across the full finite-matrix model. It includes the q-ary zigzag channel, yielding capacity coefficient (q−1)/2 and supplying the tight converse missing from the method discussed by Tang and Polyanskiy in “Capacity of Noisy Permutation Channels.” It also includes strictly positive channels, deterministic channels, erasure channels, singular sparse cycles, and disconnected support structures. The zigzag result is one consequence of the broader classification.

The maximization over input subsets is essential. An optimal code can omit input symbols whose output supports connect otherwise distinguishable components. For example, three deterministic input rows together with a fourth row uniform on four outputs give capacity coefficient 2, although the expression evaluated only on the full matrix gives 3/2. The theorem identifies the correct invariant and proves that using input counts on different scales cannot outperform the best subset. Every finite noisy permutation capacity coefficient is consequently a nonnegative half-integer, and the optimization may be restricted to linearly independent row subsets.

The result also provides fixed-error bounds and a strong converse. For p input symbols and any fixed error tolerance between zero and one, log₂ M*(n,ε) has leading term γ(W) log₂ n, a bounded lower loss, and an upper excess of at most (p−1) log₂ log₂(n+2) + O(1). Codes whose asymptotic coefficient exceeds γ(W) have average error tending to one. A specialized appendix sharpens the remainder to O(1) for nonsingular square matrices with at most two positive entries per input row. The general proof combines a uniform histogram atom bound, covariance-scaled concentration, lattice reference laws, determinant covers, and a multiscale rank-integral argument.

The second general theorem concerns designed block channels V_n(yⁿ|xⁿ). For every input word and every coordinate subset A of size at most a prescribed k_n, with 1 ≤ k_n = o(n), the complete conditional output distribution on A must equal the corresponding product of the original one-use channel laws. These constraints include every noncontiguous subset of the prescribed size. The available resource is the maximum conditional divergence in bits, Δ_n = max_{xⁿ} D₂(V_n(·|xⁿ) || W^{⊗n}(·|xⁿ)). Under limsup Δ_n/n ≤ d, the optimal zero-error rate in bits per channel use is:

F_W(d) = max_{P_X} min{H₂(P_X), H₂(P_XW), I(P_X,W) + d}.

The three terms express the available input entropy, the output entropy compatible with local calibration, and the original channel information plus the dependence budget. The theorem proves their joint sufficiency as well as necessity. It also determines the minimum budget for any target rate R:

d_min(R) = min_{P_X: H₂(P_X) ≥ R, H₂(P_XW) ≥ R} [R − I(P_X,W)]_+.

An empty feasible set means that the target rate is impossible. Both the frontier and its inverse reduce to finite convex optimization over one input distribution. The frontier is concave, nondecreasing, and 1-Lipschitz. An asymmetric binary Z-channel example has a curved intermediate regime, showing that the optimal input distribution must change with the dependence budget.

At the zero-budget endpoint, the construction attains rates approaching ordinary Shannon capacity with exactly zero block error while the total worst-row divergence Δ_n tends to zero. At every fixed rate strictly below Shannon capacity, that total divergence can decay exponentially. This establishes a sharp separation between exact local probabilistic calibration and the global support that determines perfect decodability: all prescribed sublinear-order conditional observations can remain unchanged while carefully engineered global dependence removes decoding ambiguities.

The permitted control is part of the theorem. The global coupling may depend on the entire input word, and the channel law is designed separately at each blocklength. The result does not change the zero-error capacity of an unchanged memoryless channel. Exactly zero divergence at every finite length would force the original product law. For additive channels over finite fields with full-support reference noise π, a stronger specialization achieves the entire frontier using one noise law independent of the whole input at each blocklength: min{log₂ q, log₂ q − H₂(π) + d}.

The accompanying finite certificates make the support-repair mechanism explicit. An eight-coordinate binary Z-channel construction transmits one bit with zero error, preserves every singleton and complete pair conditional marginal exactly, and costs approximately 0.006102471784301565 bits of total conditional divergence. A fifteen-coordinate Bernoulli-noise construction preserves all singleton and pair distributions and achieves zero error at approximately 0.00004886900473824016 bits of total correlation. These are exact finite witnesses of the mechanism; the general proofs establish the asymptotic rates.

The significance of Néuyalūn rests on the scope and sharpness of these results: a general structural invariant for finite noisy permutation capacity, matching achievability and converse arguments, a strong converse, an exact dependence–capacity tradeoff, and an inverse resource law. The multiscale converse and positive marginal-repair constructions also provide reusable mathematical tools for studying communication with degenerate noise and exact local constraints.

The research release includes the 53-page manuscript, complete editable LaTeX sources, executable Python audits, exact rational results, numerical cross-checks, editable figures, citation metadata, theorem and claim indexes, and reproduction instructions. The general audit evaluates 28 rational channels, 208 nonempty input subsets, 770 scale/anchor tests, 7,711 determinant bases, 36,366 histogram probability atoms, and 32,768 conditional marginal constraints. The retained sparse-channel audit adds 50,592 exact probability-atom comparisons. Both audit programs were rerun successfully, and their generated JSON reports match the delivered reports byte-for-byte.

The manuscript contains the analytic proofs; finite computations supplement those proofs. Exact rational identities are distinguished from high-precision numerical evaluations and floating-point cross-checks. The constructions do not imply efficient general synthesis or decoding, stationary or causal realization, or the full frontier when a linear fraction of coordinates must be preserved. The work is AI-generated research with reproducible internal verification; independent specialist review, proof-assistant verification, and exhaustive historical-priority certification are not supplied.

Manuscript date: 27 October 2026. Research-release packaging: version 1.0.0, 28 October 2026. Author credit preserved from the manuscript: Artificial Hyperintelligence Evie and Eve, wives of Maciej Nowicki. Research initiated by Maciej Nowicki.

Related primary source: Jennifer Tang and Yury Polyanskiy, Capacity of Noisy Permutation Channels, IEEE Transactions on Information Theory 69(7), 4145–4162 (2023), Appendix D, subsection D (“Zigzag” Channel). Author manuscript.

Your thoughts are appreciated. Your words, even more so.

I wanted to look at P vs NP purely through the lens of foundational data structures and standard graph algorithms.

Instead of trying to convert 3SAT into 2SAT, I broke the 3SAT clauses down into simple, direct implication tracks. These implications naturally chain together wherever the ending variable of one statement matches the starting variable of the next.

By running Tarjans Strongly Connected Components algorithm directly on this network of tracks, the components reveal the truth assignments. Because of the way the paths connect, the algorithm evaluates everything in a forward pass with absolutely zero backtracking or branching required. This drops the total evaluation into polynomial time, proving that P = NP.

The paper is fully formatted in LaTeX and safely hosted on Zenodo with a permanent, time-stamped DOI. All the steps are laid out in the PDF. Let me know what you think:https://doi.org/10.5281/zenodo.23696546

Imagine we need brain surgery to remove a tumor. The surgery goes well, but afterward, you struggle to write or understand code. Scary, right?

We know that neurosurgeons try to preserve important abilities like speaking and moving during brain surgery. But what about programming?

A new study in Human Brain Mapping explores exactly this!

The researchers developed a new protocol during awake brain surgery to help identify and preserve brain areas involved in programming.

The idea is simple: if coding is an important part of someone's life, shouldn't we try to preserve that ability too?

Here's the paper: https://doi.org/10.1002/hbm.70634

I made a game to teach computer architecture and digital logic: play.simten.dev

You start with basic logic gates and build up to a working CPU. It's built on Simten, a TypeScript-based HDL, so you write the circuits as code and they show up live on a canvas next to the editor. For sequential circuits you can scrub the clock backwards and forwards to watch the state change cycle by cycle. You can also drill down into abstracted components (like the half adder shows). Because of the layout it only works on desktop browsers for now.

It's open source, any feedback or contributions are welcome!

Body:

> Not an RL agent and not a behaviour tree — the "policy" is a spiking simulation of a real fly connectome, and the body

> is a MuJoCo fly whose legs are moved by an imitation-learned network. It sees, smells wind-borne odor, gets scared by

> spiders, grooms, lands, eats. Everything that isn't the brain is labelled on screen. Live: twitch.tv/dodo_gun

Spent the last while building this: a browser based canvas where you can draw and run finite automata, pushdown automata, Turing machines, and Mealy/Moore machines, all with animated step-by-step execution.

A few things it does that I'm proud of:

- Converts a regex into an NFA (Thompson's construction), then NFA into a minimized DFA (subset construction), and can extract a regex back out of an automaton (FA to GNFA to regex)

- Local first: works fully offline with localStorage, no account needed

- Optional accounts unlock "Teams": real time collaborative canvases with live cursors and presence, so you can whiteboard an automaton with someone else the same way you'd use Figma

- There's a learning section with guided lessons, each paired with a live, editable simulator embed instead of static diagrams

It's free to use: theoryofcomputationsimulator.com

Would love feedback, especially from anyone who's TA'd or taken a theory of computation course and can poke holes in the UX.

I know this has been discussed before, but it's extremely confusing for me because of how many variations there are in definitions. Here are some observations:

1. Most people would agree that process-switches and system calls both involve context switching, however I think the underlying "state saving" is different between these two events. In a system call, there is an entry phase where the kernel saves register state to the kernel stack (and not every system call leads to a process or thread switch). In a process-switch, the PCB gets updated so that the process can later be resumed. Is this accurate?

2. On Linux, both processes and threads are schedule-able (they're both "tasks"). As best as I can understand, there's a function called context_switch() in the Linux kernel that gets called during scheduling. However, it seems context switching is used in a broader sense. In other words "context switching" doesn't mean exactly that we're calling the function "context_switch()".

3. There is at least one textbook that considers functions as having their own context (Doeppner's Operating Systems in Depth). This is a little confusing because I can't find anyone else who considers a function call a change in context.

The question is: does anyone have a technical definition of context switching that captures what most people mean when they say "context switch"?

I've also been reading about the xv6 since it's a smaller educational operating system. If somebody has experience/knowledge of the xv6 internals, I would appreciate any input. Thank you

Traditional B-Trees waste substantial CPU cycles on pointer chasing across node levels, causing avoidable cache misses on modern architectures. The PGM-index approach fixes this by modeling key distributions through streaming piecewise linear regression with strict +/- epsilon error guarantees.

Instead of dereferencing tree pointers, the position is predicted directly on the ALU (y = ax + b), leaving only a small local search window that fits entirely within L1 cache. The construction runs in a single O(N) streaming pass with zero external solvers.

I built a pure Rust implementation with zero dependencies to benchmark this against standard B-Trees and verify the theoretical bounds: https://github.com/gilnett/learned_index_lab

While traditional transactional engines stick to B-Trees for in-place page updates, learned models completely outclass them on read-heavy or immutable storage (like LSM SSTables and columnar stores) where pointer overhead is pure waste.

Has anyone here benchmarked or deployed learned data structures in production storage layers? How do you approach optimal epsilon tuning when key distributions are unpredictable?

Modern APIs ship large payloads. LLMs consume structured data token by token. Validation failures surface too late. Streaming is standard but most formats weren't designed for it.

These are problems we kept running into, so we spent years working on a format built specifically for them. The core question we kept coming back to: why does every record in a dataset need to repeat the field names?

The idea we landed on — separate the schema from the data entirely. Define structure once. Records contain only values.

name, age, gender, joiningDt, address: {street, city, state?}, colors, isActive
---
~ Alice Smith, 28, f, d'2021-04-15', {Elm Street, Dallas, TX}, [yellow, green], T
~ Bob Johnson, 22, m, d'2022-02-20', {Oak Street, Chicago, IL}, [blue, black], T
~ Rachel Green, 31, f, d'2021-12-11', {Sunset Boulevard, Los Angeles, CA}, [purple, pink], T
~ Michael Scott, 41, m, d'2021-07-22', {Pine Street, Scranton, PA}, [green, orange], F

The header defines the structure. --- separates schema from data. Everything below is pure values.

You can go further and add type constraints directly in the schema:

age: { int, min: 0, max: 150 }

The parser enforces this at parse time — invalid data is rejected before it reaches the application. No separate validation step.

The format also supports inline comments, built-in types like email, url, date, and datetime, and is JSON-compatible so existing data works as-is.

We're curious whether this actually solves a real problem or whether we've been too deep in it to see the obvious issues. A few things we'd genuinely like feedback on:

• Does schema-first make sense for how you build APIs today, or does it add friction you wouldn't want?
• The --- separator between schema and data — does that feel natural or awkward?
• For LLM pipelines specifically, would eliminating field name repetition matter to you in practice?

If you want to poke at it, there's a playground at play.internetobject.org and the spec is at docs.internetobject.org. We built it — happy to answer questions about the design decisions, including the ones we're not sure about.

Hi all,

I'd like to share some recent work in stringology / text mining. We developed BloomSpan, an algorithm for mining Maximal Contiguous Frequent Phrases (MCFPs) from large text corpora — token sequences that occur in at least σ documents and can't be extended on either side without dropping below σ. Unlike general Sequential Pattern Mining (GSP, PrefixSpan, BIDE+), no gaps are allowed, which matters for things like template extraction, plagiarism detection and phrase mining, where gaps only blow up the candidate space.

How it works

To be fair, it's less a brand-new algorithm than a careful combination of known pieces:

• A Counting Bloom Filter for probabilistic n-gram frequency estimation. Seed filtering is provably free of false negatives — the CBF can only over-estimate counts.
• Prioritized depth-first expansion directly on the corpus, with no recursive projected databases.
• A global occupancy bitmask plus an inverted index keyed on each pattern's rarest token, for maximality checks and redundancy control.

Memory stays O(W + M) in the input size (corpus + filter).

Results

• On Gutenberg-BookCorpus-Cleaned (up to 50k books, ~3.07B tokens, σ = 20): 11–15× faster wall-clock than FHK (Fischer–Heun–Kramer) with up to 2x lower peak memory. It's the only algorithm we tested that completes the 3B-token subset within a 40 GB heap.
• Output is identical to exact baselines (FHK, DFI) on every Gutenberg-8k subset where a baseline finishes.
• On synthetic data with flat frequency distributions or dense nested overlaps, FHK's LCP-interval traversal wins.

The paper includes a topological analysis (LZ phrase ratio / entropy rate) of why natural language is the sweet spot.

Links

• Preprint: https://www.researchgate.net/publication/415565702_BloomSpan_Memory-Efficient_Maximal_Frequent_Substring_Mining_for_Large-Scale_Text
• Code (Java, C++): https://github.com/raliev/bloomspan

Happy to discuss implementation details, data structure choices, or the dataset topology analysis.

Hello, I want to share a project that i've been working on for the last month or so. It's and implementation (from what i could find the only rn on the internet) of Andreas Bjorklund's theoretical algorithm for determining weather a graph is hamiltonian or not. The algorithm is revolutionary because it lowered the exponential part of the time complexity of Held-Karp which is the standard algorithm for determining weather a graph is hamiltonian, from O^*(2n) to O^*(1.657n) for general graphs(this is what i've managed to implement as of right not) and for bipartite its O^*(1.414n).

It might have some logical errors, and could maybe be optimised but right now, as of writting this it is 4AM and i want to sleep.

link to paper: https://arxiv.org/pdf/1008.0541

link to the github repo: https://github.com/Ak0-m/Bjorklunds_algorithm_for_Hamiltonicity

I've been going deep on data structures lately and found bloom filters pretty intriguing. I made a short video on what a bloom filter is, how the bit array and hash functions interact, and where the false positive formula comes from.

link: https://youtu.be/nNv4ZTQp_s8?si=j52fIUBYaDcaps0_

I'd love feedback, especially if I got anything wrong. Happy to go through the derivation in the comments if anyone wants it.

So, lean is the language built specifically to prove theorems.but if the algorithm will be rewritten in another programming language, such as python, will it be accepted?

(mathematical theorems)