論文の概要: The Approximate Degree of DNF and CNF Formulas

• arxiv url: http://arxiv.org/abs/2209.01584v1
• Date: Sun, 4 Sep 2022 10:01:39 GMT
• ステータス: 処理完了
• システム内更新日: 2023-01-27 23:24:36.362454
• Title: The Approximate Degree of DNF and CNF Formulas
• Title（参考訳）: DNFとCNFの近似値
• Authors: Alexander A. Sherstov
• Abstract要約: すべての$delta>0に対して、$はCNFと近似次数$Omega(n1-delta)の式を構築し、基本的には$nの自明な上限に一致する。 すべての$delta>0$に対して、これらのモデルは$Omega(n1-delta)$、$Omega(n/4kk2)1-delta$、$Omega(n/4kk2)1-delta$が必要です。
• 参考スコア（独自算出の注目度）: 95.94432031144716
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The approximate degree of a Boolean function $f\colon\{0,1\}^n\to\{0,1\}$ is the minimum degree of a real polynomial $p$ that approximates $f$ pointwise: $|f(x)-p(x)|\leq1/3$ for all $x\in\{0,1\}^n.$ For every $\delta>0,$ we construct CNF and DNF formulas of polynomial size with approximate degree $\Omega(n^{1-\delta}),$ essentially matching the trivial upper bound of $n.$ This improves polynomially on previous lower bounds and fully resolves the approximate degree of constant-depth circuits ($\text{AC}^0$), a question that has seen extensive research over the past 10 years. Previously, an $\Omega(n^{1-\delta})$ lower bound was known only for $\text{AC}^0$ circuits of depth that grows with $1/\delta$ (Bun and Thaler, FOCS 2017). Moreover, our CNF and DNF formulas are the simplest possible in that they have constant width. Our result holds even for one-sided approximation, and has the following further consequences. (i) We essentially settle the communication complexity of $\text{AC}^0$ circuits in the bounded-error quantum model, $k$-party number-on-the-forehead randomized model, and $k$-party number-on-the-forehead nondeterministic model: we prove that for every $\delta>0$, these models require $\Omega(n^{1-\delta})$, $\Omega(n/4^kk^2)^{1-\delta}$, and $\Omega(n/4^kk^2)^{1-\delta}$, respectively, bits of communication even for polynomial-size constant-width CNF formulas. (ii) In particular, we show that the multiparty communication class $\text{coNP}_k$ can be separated essentially optimally from $\text{NP}_k$ and $\text{BPP}_k$ by a particularly simple function, a polynomial-size constant-width CNF. (iii) We give an essentially tight separation, of $O(1)$ versus $\Omega(n^{1-\delta})$, for the one-sided versus two-sided approximate degree of a function; and $O(1)$ versus $\Omega(n^{1-\delta})$ for the one-sided approximate degree of a function $f$ versus its negation $\neg f$.
• Abstract（参考訳）: ブール関数 $f\colon\{0,1\}^n\to\{0,1\}$ の近似次数は、実多項式 $p$ の最小次数であり、f$ に近似する: $|f(x)-p(x)|\leq1/3$ すべての$x\in\{0,1\}^n に対して。 任意の $\delta>0 に対して、$$ は概算次数 $\Omega(n^{1-\delta}) の多項式サイズの CNF と DNF の公式を構築し、$ は本質的に$n の自明な上限に一致する。 これは以前の下界の多項式的に改善され、過去10年間に広範な研究がなされた質問である定数深度回路の近似次数 ("\text{AC}^0$") を完全に解決する。 以前は、$\Omega(n^{1-\delta})$ lower bound は $\text{AC}^0$ の深さの回路でしか知られておらず、1/\delta$ (Bun and Thaler, FOCS 2017) で成長する。 さらに,我々のCNF式とDNF式は,その幅が一定である場合に最も単純である。 この結果は一方的な近似においても成り立ち、次の結果をもたらす。 i) 基本的には、有界エラー量子モデルにおける$\text{AC}^0$回路、$k$-party number-on-the-foreheadランダム化モデルおよび$k$-party number-on-the-forehead非決定論的モデルにおける通信複雑性を解決している: すべての$\delta>0$に対して、これらのモデルは$\Omega(n^{1-\delta})$, $\Omega(n/4^k^2)^{1-\delta}$, $\Omega(n/4^k^2)^{1-\delta}$, $\Omega(n/4^k^2)^{1-\delta}$, (ii)特に、マルチパーティ通信クラス $\text{conp}_k$ は、特に単純な関数である多項式サイズの定数幅 cnf によって、$\text{np}_k$ と $\text{bpp}_k$ とを本質的に最適に分離できることを示す。 (iii) 関数の一辺近似次数に対して$O(1)$対$\Omega(n^{1-\delta})$、関数の一辺近似次数に対して$O(1)$対$\Omega(n^{1-\delta})$、関数の一辺近似次数に対して$O(1)$対$Omega(n^{1-\delta})$という本質的に厳密な分離を与える。

関連論文リスト

• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。 アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
  論文  参考訳（メタデータ） (2024-10-26T06:21:42Z)
• On the Complexity of Finite-Sum Smooth Optimization under the Polyak-{\L}ojasiewicz Condition [14.781921087738967]
  本稿では、$min_bf xinmathbb Rd f(bf x)triangleq frac1nsum_i=1n f_i(bf x)$, ここで、$f(cdot)$はパラメータ$mu$と$f_i(cdot)_i=1n$は$L$-mean-squared smoothである。
  論文  参考訳（メタデータ） (2024-02-04T17:14:53Z)
• $\ell_p$-Regression in the Arbitrary Partition Model of Communication [59.89387020011663]
  コーディネータモデルにおける分散$ell_p$-regression問題のランダム化通信複雑性について考察する。 p = 2$、すなわち最小二乗回帰の場合、$tildeTheta(sd2 + sd/epsilon)$ bitsの最初の最適境界を与える。 p in (1,2)$ に対して、$tildeO(sd2/epsilon + sd/mathrmpoly(epsilon)$ upper bound を得る。
  論文  参考訳（メタデータ） (2023-07-11T08:51:53Z)
• 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)
• 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)
• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
  S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。 十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
  論文  参考訳（メタデータ） (2020-06-06T13:34:41Z)
• A closer look at the approximation capabilities of neural networks [6.09170287691728]
  1つの隠れた層を持つフィードフォワードニューラルネットワークは、任意の連続関数$f$を任意の近似しきい値$varepsilon$に近似することができる。 この均一な近似特性は、重量に強い条件が課せられているにもかかわらず、依然として維持されていることを示す。
  論文  参考訳（メタデータ） (2020-02-16T04:58:43Z)
• On the Complexity of Minimizing Convex Finite Sums Without Using the Indices of the Individual Functions [62.01594253618911]
  有限和の有限ノイズ構造を利用して、大域オラクルモデルの下での一致する$O(n2)$-upper境界を導出する。 同様のアプローチを踏襲したSVRGの新規な適応法を提案し、これはオラクルと互換性があり、$tildeO(n2+nsqrtL/mu)log (1/epsilon)$と$O(nsqrtL/epsilon)$, for $mu>0$と$mu=0$の複雑さ境界を実現する。
  論文  参考訳（メタデータ） (2020-02-09T03:39:46Z)

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

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