Fugu-MT 論文翻訳(概要): Rational degree is polynomially related to degree

論文の概要: Rational degree is polynomially related to degree

arxiv url: http://arxiv.org/abs/2601.08727v1
Date: Tue, 13 Jan 2026 16:57:02 GMT
ステータス: 翻訳完了
システム内更新日: 2026-01-14 18:27:19.297093
Title: Rational degree is polynomially related to degree
Title（参考訳）: 有理次数は次数に多項式的に関連している
Authors: Matt Kovacs-Deak, Daochen Wang, Rain Zimin Yang,
Abstract要約: for every Boolean function $f$, where $mathrmdeg(f)$ is the degree of $f$ and $mathrmrdeg(f)$ is the rational degree of $f$。
参考スコア（独自算出の注目度）: 1.5420873135976756
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We prove that $\mathrm{deg}(f) \leq 2 \, \mathrm{rdeg}(f)^4$ for every Boolean function $f$, where $\mathrm{deg}(f)$ is the degree of $f$ and $\mathrm{rdeg}(f)$ is the rational degree of $f$. This resolves the second of the three open problems stated by Nisan and Szegedy, and attributed to Fortnow, in 1994.
Abstract（参考訳）: 我々は、すべてのブール関数に対して $\mathrm{deg}(f) \leq 2 \, \mathrm{rdeg}(f)^4$ を証明し、ここで $\mathrm{deg}(f)$ は$f$ の次数であり、$\mathrm{rdeg}(f)$ は$f$ の有理次数である。これはニサンとセゲディによって述べられた3つの開問題のうちの2つを解決し、1994年にFortnowに帰せられている。

関連論文リスト

A Degree Bound for the c-Boomerang Uniformity [2.538209532048867]
F$の$c$-Boomerang, $c neq 0$は、-$d2$ if $c2 neq 1$, - $d cdot (d - 1)$ if $c = -1$, - $d cdot (d - 2)$ if $c = 1$であることを示す。
論文参考訳（メタデータ） (2025-10-21T10:45:35Z)
PREM: Privately Answering Statistical Queries with Relative Error [91.98332694700046]
合成データを生成する新しいフレームワークである$mathsfPREM$(Private Relative Error Multiplicative weight update)を紹介します。我々はアルゴリズムをほぼ一致する下界で補完する。
論文参考訳（メタデータ） (2025-02-20T18:32:02Z)
The Differential and Boomerang Properties of a Class of Binomials [28.489574654566677]
F_2,u(x)=x2big (1+ueta(x)big)$ over $mathbbF_q$。我々は citebudaghyan 2024arithmetization において、$F_2,u$ が APN 函数であるような無限に多くの$q$ と $u$ が存在するという予想を否定する。
論文参考訳（メタデータ） (2024-09-21T23:33:00Z)
When does a bent concatenation not belong to the completed Maiorana-McFarland class? [47.2382573252527]
曲がった結合 $f$ (not) は、完了した Maiorana-McFarland クラス $mathcalM#$ に属するのか? 私たちは$mathcalM#$の外で曲がった関数を指定する方法を示します。
論文参考訳（メタデータ） (2024-04-24T21:36:19Z)
On the Rational Degree of Boolean Functions and Applications [2.929575660518211]
有理次数として知られるブール関数の自然複雑性測度について検討する。量子コンピュータの場合、選択後エラーと境界エラーはブラックボックスモデルにおけるリソースであることを示す。
論文参考訳（メタデータ） (2023-10-12T03:14:44Z)
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)
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)
The quantum query complexity of composition with a relation [78.55044112903148]
Belovs は負の重み付け逆法の修正版 $mathrmADV_relpm(f)$ を与えた。関係が効率よく検証できる:$mathrmADVpm(f_a) = o(mathrmADV_relpm(f))$ for every $a in [K]$。
論文参考訳（メタデータ） (2020-04-14T12:07:20Z)

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