論文の概要: On the Rational Degree of Boolean Functions and Applications
- arxiv url: http://arxiv.org/abs/2310.08004v1
- Date: Thu, 12 Oct 2023 03:14:44 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-15 11:19:54.230016
- Title: On the Rational Degree of Boolean Functions and Applications
- Title（参考訳）: ブール関数の合理度と応用について
- Authors: Vishnu Iyer, Siddhartha Jain, Matt Kovacs-Deak, Vinayak M. Kumar, Luke
Schaeffer, Daochen Wang, Michael Whitmeyer
- Abstract要約: $mathrmrdeg(f)$ は $mathrmdeg(f)$ と無界に関係していると推測される。
対称函数は有理次数 $mathrmdeg(f)/2$ を持ち、単調函数は少なくとも有理次数 $sqrtmathrmdeg(f)$ を持つ。
- 参考スコア（独自算出の注目度）: 1.8125795677957914
- License: http://creativecommons.org/publicdomain/zero/1.0/
- Abstract: We study a natural complexity measure of Boolean functions known as the
(exact) rational degree. For total functions $f$, it is conjectured that
$\mathrm{rdeg}(f)$ is polynomially related to $\mathrm{deg}(f)$, where
$\mathrm{deg}(f)$ is the Fourier degree. Towards this conjecture, we show that
symmetric functions have rational degree at least $\mathrm{deg}(f)/2$ and
monotone functions have rational degree at least $\sqrt{\mathrm{deg}(f)}$. We
observe that both of these lower bounds are tight. In addition, we show that
all read-once depth-$d$ Boolean formulae have rational degree at least
$\Omega(\mathrm{deg}(f)^{1/d})$. Furthermore, we show that almost every Boolean
function on $n$ variables has rational degree at least $n/2 - O(\sqrt{n})$.
In contrast to total functions, we exhibit partial functions that witness
unbounded separations between rational and approximate degree, in both
directions. As a consequence, we show that for quantum computers,
post-selection and bounded-error are incomparable resources in the black-box
model.
- Abstract（参考訳）: 実)有理次数として知られるブール関数の自然複雑性測度について検討する。
総関数 $f$ に対し、$\mathrm{rdeg}(f)$ は多項式的に$\mathrm{deg}(f)$ に関係しており、$\mathrm{deg}(f)$ はフーリエ次数である。
この予想に向けて、対称函数の有理次数は少なくとも$\mathrm{deg}(f)/2$であり、単調函数の有理次数は少なくとも$\sqrt{\mathrm{deg}(f)}$であることを示す。
これらの下限はどちらも厳密である。
さらに、すべてのリード・オンス深さ-$d$ブール公式が少なくとも$\Omega(\mathrm{deg}(f)^{1/d})$であることを示す。
さらに、$n$変数上のほとんどすべてのブール函数が少なくとも$n/2 - O(\sqrt{n})$の有理次数を持つことを示す。
全体関数とは対照的に, 有理次数と近似次数の間の非有界な分離を両方向で確認する部分関数を示す。
その結果、量子コンピュータでは、ポスト選択と境界エラーはブラックボックスモデルでは比較不能な資源であることが示される。
関連論文リスト
- The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。
アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
論文 参考訳（メタデータ） (2024-10-26T06:21:42Z) - 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) - Noncompact uniform universal approximation [0.0]
普遍近似定理は、(コンパクトでない)入力空間 $mathbbRn$ 上の一様収束に一般化される。
無限大で消えるすべての連続関数は、ニューラルネットワークによって一様に近似することができる。
論文 参考訳（メタデータ） (2023-08-07T08:54:21Z) - 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) - Learning a Single Neuron with Adversarial Label Noise via Gradient
Descent [50.659479930171585]
モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。
学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
論文 参考訳（メタデータ） (2022-06-17T17:55:43Z) - Uncertainties in Quantum Measurements: A Quantum Tomography [52.77024349608834]
量子系 $S$ に関連する可観測物は非可換代数 $mathcal A_S$ を形成する。
密度行列 $rho$ は可観測物の期待値から決定できると仮定される。
アーベル代数は内部自己同型を持たないので、測定装置は可観測物の平均値を決定することができる。
論文 参考訳（メタデータ） (2021-12-14T16:29:53Z) - How many moments does MMD compare? [7.919213739992465]
MathcalF-1$は、$K$に関連付けられた積分作用素と同じ方法で滑らかな関数に作用する。
擬微分作用素によって定義されるカーネルは、コンパクト集合上の任意の連続マーサー核を均一に近似することができることを示す。
論文 参考訳（メタデータ） (2021-06-27T16:44:17Z) - 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) - 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) - A Tight Composition Theorem for the Randomized Query Complexity of
Partial Functions [1.2284934135116514]
合成関数のランダム化クエリ複雑性に関する2つの新しい結果を示す。
すべての$f$と$g$に対して、$(Rcirc g)=Omega(mathopnoisyR(f)cdot R(g))$, ここで$mathopnoisyR(f)$は、ノイズ入力に対する$f$の計算コストを表す尺度である。
論文 参考訳（メタデータ） (2020-02-25T11:58:14Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。