論文の概要: On the Approximate Non-Deterministic Degree of Total Boolean Functions

• arxiv url: http://arxiv.org/abs/2605.23336v1
• Date: Fri, 22 May 2026 07:52:09 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-25 17:29:20.252469
• Title: On the Approximate Non-Deterministic Degree of Total Boolean Functions
• Title（参考訳）: 総ブール関数の近似的非決定論的度について
• Authors: Samruddhi Pednekar, Supartha Podder,
• Abstract要約: 関数 $f$, $mathsfndeg_(f)$ (書式 $mathsfN_(f)$ for brevity) 30年以上にわたって開かれた合理的次数予想は、最近Kothari、KovacsDeak、Wang、Yangによって解決された。
• 参考スコア（独自算出の注目度）: 0.2864713389096699
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The approximate non-deterministic degree of a Boolean function $f$, denoted $\mathsf{ndeg}_ε(f)$ (written $\mathsf{N}_ε(f)$ for brevity), is the minimum degree of a real polynomial $p$ such that $0 \le |p(x)| \le ε$ whenever $f(x) = 0$, and $|p(x)| \ge 1$ whenever $f(x) = 1$. Unlike exact non-deterministic degree, which only requires the polynomial to be nonzero on $1$-inputs, this measure enforces a uniform gap: the polynomial must stay close to zero on all $0$-inputs and bounded away from zero on all $1$-inputs. The rational degree conjecture, open for over three decades, was recently resolved by Kothari, Kovacs-Deak, Wang, and Yang, who showed that for every total Boolean function $f$, \[ deg(f) \le \widetilde O\!\left(\operatorname{rdeg}(f)^3\right). \] In their paper, they explicitly propose a stronger conjecture: that approximate degree is polynomially bounded by $\mathsf{N}_ε(f)$ and $\mathsf{N}_ε(\overline{f})$ jointly, i.e., for every total Boolean function $f$ and every constant $0<ε<1$, \[ \widetilde{deg}(f) \le \operatorname{poly}(\mathsf N_ε(f), \mathsf N_ε(\overline f)). \] This conjecture, if true, would imply a polynomial version of the rational degree result and bring us closer to resolving de Wolf's longstanding non-deterministic degree conjecture. In this work, we make the first systematic progress on this problem, establishing the conjecture for several broad and natural function classes: monotone and unate functions, functions of bounded alternation number, symmetric functions, $k$-uniform hypergraph properties, and read-$k$ Disjunctive Normal Form (DNF) formulas.
• Abstract（参考訳）: ブール関数 $f$ の近似非決定論的次数 $\mathsf{ndeg}_ε(f)$ (write $\mathsf{N}_ε(f)$ for brevity) は実多項式 $p$ の最小次で、$0 \le |p(x)| \le ε$ whenever $f(x) = 0$, and $|p(x)| \ge 1$ whenever $f(x) = 1$ である。 この測度は、多項式が1$インプットで 0 でないことだけを必要とする正確な非決定論的次数とは異なり、一様ギャップを課す:多項式はすべての$0$インプットで 0 に近づき、全ての$1$インプットで 0 から離れていなければならない。 30年以上続く有理次数予想は、最近Kothari、Kovacs-Deak、Wang、Yangによって解決され、すべてのブール関数が$f$, \[deg(f) \le \widetilde O\! \left(\operatorname{rdeg}(f)^3\right)。 例えば、すべての全ブール関数 $f$ とすべての定数 $0<ε<1$, \[\widetilde{deg}(f) \le \operatorname{poly}(\mathsf N_ε(f), \mathsf N_ε(\overline f)) に対して。 この予想は、もし真であれば、有理次数の結果の多項式バージョンを暗示し、ド・ウルフの長年の非決定論的次数予想を解こうとするものである。 本研究では、この問題を初めて体系的に進行させ、モノトーンとアンテート関数、有界交互数関数、対称関数、$k$-ユニフォームハイパーグラフ特性、read-$k$ Disjunctive Normal Form (DNF) といった、幅広い自然関数クラスの予想を確立する。

関連論文リスト

• Quantum and classical query complexities of functions of matrices [0.0]
  任意の連続関数 $f(x):[-1,1]rightarrow [-1,1]$ に対して、計算の量子クエリ複雑性 $brai f(A) ketjpm varepsilon/4$ は$Omega(widetildedeg_varepsilon(f))$ で制限される。
  論文  参考訳（メタデータ） (2023-11-13T00:45:41Z)
• On the Rational Degree of Boolean Functions and Applications [2.929575660518211]
  有理次数として知られるブール関数の自然複雑性測度について検討する。 量子コンピュータの場合、選択後エラーと境界エラーはブラックボックスモデルにおけるリソースであることを示す。
  論文  参考訳（メタデータ） (2023-10-12T03:14:44Z)
• Dimension-free discretizations of the uniform norm by small product sets [45.85600902330814]
  ベルンシュタインの古典的不等式は、単位円上の最高ノルムの$f$と、その最高ノルムの$K$-階根のサンプリング集合上の最高ノルムと比較する。 次元自由離散化は、濃度が$deg(f)$とは独立なサンプリング集合で可能であり、代わりに$f$の最大個人次数によって支配されることを示す。
  論文  参考訳（メタデータ） (2023-10-11T22:46:09Z)
• The Approximate Degree of DNF and CNF Formulas [95.94432031144716]
  すべての$delta>0に対して、$はCNFと近似次数$Omega(n1-delta)の式を構築し、基本的には$nの自明な上限に一致する。 すべての$delta>0$に対して、これらのモデルは$Omega(n1-delta)$、$Omega(n/4kk2)1-delta$、$Omega(n/4kk2)1-delta$が必要です。
  論文  参考訳（メタデータ） (2022-09-04T10:01:39Z)
• 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)
• Degree vs. Approximate Degree and Quantum Implications of Huang's Sensitivity Theorem [4.549831511476248]
  すべてのブール関数に対して、$f$, $bullet quad mathrmdeg(f) = O(widetildemathrmdeg(f)2)$:$f$の次数は、f$の近似次数において最も自明な二次数であることを示す。 f$ がその隣接行列で指定される $n$-頂点グラフの非単調グラフ特性であるならば、$mathrmQ(f)=Omega(n)$ もまた最適である。
  論文  参考訳（メタデータ） (2020-10-23T19:21:28Z)
• 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)

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

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