論文の概要: Boolean threshold functions, neuron capacity, and memory retrieval

• arxiv url: http://arxiv.org/abs/2609.29756v1
• Date: Thu, 24 Sep 2026 13:06:03 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-25 21:10:09.944103
• Title: Boolean threshold functions, neuron capacity, and memory retrieval
• Title（参考訳）: ブール閾値関数、ニューロン容量、記憶検索
• Abstract要約: 閾値関数 $f(x)=operatornamesgn(a_0+langle a,xrangle)$, $xin-1,1n$ はいくつあるかを示す。 Kanter--Sompolinsky Hamiltonianのメモリ検索の文脈では、$r=n-1$がシャープしきい値である。
• 参考スコア（独自算出の注目度）: 0.11280931253550518
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: How much information can a single neuron remember? How many memories can neural networks retrieve without creating false memories? These questions are related to a basic question: how many Boolean threshold functions $f(x)=\operatorname{sgn}(a_0+\langle a,x\rangle)$, $x\in\{-1,1\}^n$, are there? In this paper, we show that the number $T_n$ of distinct Boolean threshold functions is \[ T_n=2\binom{2^n-1}{n}\bigl(1+O(n^{-99})\bigr). \] Equivalently, the capacity of a single threshold neuron is $n^2-\log_2(n!)+1+O(n^{-99})$ bits, improving the $O(n)$ error term in the result of Kahn--Komlós--Szemerédi to $O(n^{-99})$. To prove this, we show that, for $1\le r\le n-1$, and $v_1,\ldots,v_r$ are chosen at random from $\{-1,1\}^n$, \[ \mathbb P\!\left\{ \langle v_1,\ldots,v_r\rangle\cap\{-1,1\}^n =\{\pm v_1,\ldots,\pm v_r\} \right\} =1-O(n^{-99}). \] In the context of the Kanter--Sompolinsky Hamiltonian for memory retrieval, this identifies $r=n-1$ as a sharp threshold, at which, for almost every collection of $r$ memories, the only ground states are these memories and their negatives, confirming a weaker form of the Kalai--Linial--Odlyzko conjecture. It also settles a recent open problem posed by M. Anthony on the specification number of Boolean threshold functions. In addition, we show that, for every $1\le r\le n-1$, \[ \mathbb P\{v_1,\ldots,v_r\text{ are linearly dependent}\} =2\binom r2\,2^{-n}+O\!\left(2^{-n}e^{-cn}\right), \] confirming a conjecture of Kahn--Komlós--Szemerédi.
• Abstract（参考訳）: 1人のニューロンがどれだけの情報を覚えることができるか? ニューラルネットワークが偽の記憶を作らずに回復できる記憶はいくつあるか? ブールしきい値関数 $f(x)=\operatorname{sgn}(a_0+\langle a,x\rangle)$, $x\in\{-1,1\}^n$ はいくつあるか? 本稿では,異なるブールしきい値関数の$T_n$ が \[T_n=2\binom{2^n-1}{n}\bigl(1+O(n^{-99})\bigr であることを示す。 同様に、1つの閾値ニューロンの容量は$n^2-\log_2(n!)+1+O(n^{-99})$ bitsであり、Kahn--Komlós--Szemerédi の結果として$O(n)$エラー項を $O(n^{-99})$に改善する。 これを証明するために、$\le r\le n-1$ と $v_1,\ldots,v_r$ は ${-1,1\}^n$, \[ \mathbb P\! \left\{ \langle v_1,\ldots,v_r\rangle\cap\{-1,1\}^n =\{\pm v_1,\ldots,\pm v_r\} \right\} =1-O(n^{-99})。 メモリ検索におけるカンター-ソムポリンスキー・ハミルトニアン(英語版)の文脈では、これは$r=n-1$をシャープしきい値とし、そこでは、$r$のほとんどすべてのコレクションにおいて、基底状態はこれらのメモリとその負のみであり、Kalai-Linial-Odlyzko予想の弱い形式を確認する。 また、M. Anthony によるブールしきい値関数の仕様数に関する最近の開問題も解決している。 さらに、1ドル r\le n-1$ に対して、 \[ \mathbb P\{v_1,\ldots,v_r\text{ は線型依存}\} = 2\binom r2\,2^{-n}+O\! \left(2^{-n}e^{-cn}\right), \] はケーン=コムロシュ=シェメレディ予想を裏付ける。

関連論文リスト

• Sparse Quantum State Preparation with Sublinear T-Count [5.929956715430168]
  $$n$-qubit $s$-sparse状態は、$widetildeO(mins, n3/4sqrts+sqrtslog (1/)+log (1/)$ $T$ gatesを使ってエラーを発生させることができる。 0le$と2le sle 2n/2$に対して、スパース状態の準備には$(mins,sqrtns)$$Tが必要である。
  論文  参考訳（メタデータ） (2026-08-01T03:33:19Z)
• Rényi exponent landscape of multipartite entanglement in free-fermion systems [51.56484100374058]
  我々は、Rényi tripartite information $I_3() が小フェルミ運動量での質的に $exclusion-dependent scaling を示すことを示した。 I_m(n)/I_m(1) sim zm-1 to 0$ for all integer $n geq 2$, so the leading von Neumann signal can builded from integer Rényi data。
  論文  参考訳（メタデータ） (2026-03-09T22:27:00Z)
• An Efficient Computational Framework for Discrete Fuzzy Numbers Based on Total Orders [41.99844472131922]
  我々は、$textitpos$関数を計算するために、合計(許容可能な)順序の構造を利用するアルゴリズムを導入する。 提案手法は、下層の鎖の大きさの2乗である$mathcalO(n2 m log n)$の複雑さを実現する。 その結果、この定式化は計算コストを大幅に削減することを示した。
  論文  参考訳（メタデータ） (2025-11-21T09:35:07Z)
• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。 アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
  論文  参考訳（メタデータ） (2024-10-26T06:21:42Z)
• Enlarging the notion of additivity of resource quantifiers [62.997667081978825]
  量子状態 $varrho$ と量子化器 $cal E(varrho) が与えられたとき、$cal E(varrhootimes N)$ を決定するのは難しい。 本研究では, ある球対称状態の1発の蒸留可能な絡み合いを, このような拡張付加性によって定量的に近似できることを示す。
  論文  参考訳（メタデータ） (2022-07-31T00:23:10Z)
• Low-degree learning and the metric entropy of polynomials [44.99833362998488]
  少なくとも$Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon)は2辺の推定値$c(1-varepsilon)2dlogを満たす。
  論文  参考訳（メタデータ） (2022-03-17T23:52:08Z)
• Learning low-degree functions from a logarithmic number of random queries [77.34726150561087]
  任意の整数 $ninmathbbN$, $din1,ldots,n$ および任意の $varepsilon,deltain(0,1)$ に対して、有界関数 $f:-1,1nto[-1,1]$ に対して、少なくとも$d$ の次数を学ぶことができる。
  論文  参考訳（メタデータ） (2021-09-21T13:19:04Z)
• Exponential Lower Bounds for Threshold Circuits of Sub-Linear Depth and Energy [0.0]
  しきい値回路$C$ of size $s$, depth $d$, energy $e$ and weight $w$ satisfies $log (rk(M_C)) le ed。 離散化ReLE回路や復号化シグモノイド回路などの他のニューラルネットワークのモデルに対しては、同様の不等式が離散化回路の$C$についても成り立つことを証明している。
  論文  参考訳（メタデータ） (2021-07-01T05:37:53Z)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
  論文  参考訳（メタデータ） (2020-08-24T06:50:57Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。