Fugu-MT 論文翻訳(概要): Non-Local Search-to-Decision Reduction over F2

論文の概要: Non-Local Search-to-Decision Reduction over F2

arxiv url: http://arxiv.org/abs/2608.19091v1
Date: Wed, 19 Aug 2026 16:40:55 GMT
ステータス: 翻訳完了
システム内更新日: 2026-08-20 20:13:55.463829
Title: Non-Local Search-to-Decision Reduction over F2
Title（参考訳）: F2上の非局所探索-決定還元
Abstract要約: 非局所的な探索-決定は、一様ランダムな文字列の二部符号の2つの共有が同じランダムなパリティを予測できるかどうかを問う。局所的な測定で 2 つの $x$ を回復する最適確率が$p$ であれば、共通のパリティ問題に正しく答える確率は、少なくとも $min1,frac12+5p1/22$ である。
参考スコア（独自算出の注目度）: 4.646615583337459
License: http://creativecommons.org/licenses/by/4.0/
Abstract: Non-local search-to-decision asks whether two noncommunicating parties, given the two shares of a bipartite encoding of a uniformly random string $x\in \mathbb{F}_2^n$, can both predict the same random parity $\langle r,x\rangle$ without there also being local measurements with which both parties recover $x$. We prove that if their optimal probability of both recovering $x$ by local measurements is $p$, then their probability of both answering a common parity challenge correctly is at most $\min\{1,\frac{1}{2}+5p^{1/22}\}$. The result is motivated by applications to unclonable encryption and quantum copy-protection. The proof is information-theoretic and does not provide an efficient extractor. The proof and the exposition were developed with assistance from ChatGPT using GPT-5.6 Sol Pro and Codex in the Ultra reasoning mode.
Abstract（参考訳）: 非局所的な探索 to 決定は、2つの非通信相手に対して、一様ランダムな文字列 $x\in \mathbb{F}_2^n$ の2つの二部符号が同じランダムなパリティ$\langle r,x\rangle$ を予測できるかどうかを問う。局所的な測定で 2 つの $x$ を回復する最適確率が$p$ であれば、共通のパリティ問題に正しく答える確率は、最大$\min\{1,\frac{1}{2}+5p^{1/22}\}$ である。この結果は、制限不能な暗号化と量子コピー保護へのアプリケーションによって動機付けられている。この証明は情報理論であり、効率的な抽出器を提供しない。証明と展示は、GPT-5.6 Sol ProとCodexをウルトラ推論モードで使用してChatGPTの助けを借りて開発された。

関連論文リスト

Small-Bias Quantum Approximate Counting via the Multiplicative Adversary Method [1.2799130177714182]
量子近似カウントの2重決定版について検討する。オラクルが$xin0,1N$にアクセスすると、$|x|=M$と$|x|=M+$を区別する。乗法逆法を用いて、$left(maxleftsqrt(N-M)(M+)/,sqrtN/rightright)$を証明する。
論文参考訳（メタデータ） (2026-09-09T07:01:11Z)
Efficient Unclonable Encryption from Pauli Eigenstates [2.0305676256390934]
私たちは、私たちの知る限り、最初のプレーンモデル、ワンタイムの情報-理論上は安全で、効率の悪い暗号化スキームを1ビットで提供します。鍵は$n$ qubits上の一様ランダム位相自由パウリであり、ビット$a$はそのパウリの固有状態のランダム$(-1)a$として暗号化される。両受信機がビットを回復する確率は、少なくとも$frac12+frac12sqrt2n/(4n-1)であることを示す。
論文参考訳（メタデータ） (2026-07-23T20:53:24Z)
Sign Operator for Coping with Heavy-Tailed Noise in Non-Convex Optimization: High Probability Bounds Under $(L_0, L_1)$-Smoothness [74.18546828528298]
SignSGD with Majority Votingは,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappaka ppakappa-1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappakappa -1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappappapa-1right,Kappaを用いて,複雑性の全範囲で堅牢に動作することを示す。
論文参考訳（メタデータ） (2025-02-11T19:54:11Z)
Tripartite Haar random state has no bipartite entanglement [2.8271134123622064]
本研究では,EPR様二部晶の絡み合いを三部晶のハールランダム状態から蒸留することは不可能であることを示す。 EPRに類似したエンタングルメントを持つ状態のサンプリングの確率を、所定のEPR忠実度トレランスで上界に導出する。
論文参考訳（メタデータ） (2025-02-06T19:00:01Z)
Provable Scaling Laws for the Test-Time Compute of Large Language Models [84.00141420901038]
本研究では,大規模言語モデルのテスト時間計算において,証明可能なスケーリング法則を享受する2つのアルゴリズムを提案する。 1つは2段階ノックアウト方式のアルゴリズムで、各候補は複数の相手に対して平均勝利率で評価される。もう1つは2段階のリーグ方式のアルゴリズムで、各候補は複数の相手に対して平均勝利率で評価される。
論文参考訳（メタデータ） (2024-11-29T05:29:47Z)
Relative-Translation Invariant Wasserstein Distance [82.6068808353647]
距離の新しい族、相対翻訳不変ワッサーシュタイン距離(RW_p$)を導入する。我々は、$RW_p 距離もまた、分布変換に不変な商集合 $mathcalP_p(mathbbRn)/sim$ 上で定義される実距離測度であることを示す。
論文参考訳（メタデータ） (2024-09-04T03:41:44Z)
Perturb-and-Project: Differentially Private Similarities and Marginals [73.98880839337873]
差分プライバシーのための入力摂動フレームワークを再検討し、入力にノイズを付加する。まず、ペアワイズ・コサイン類似性をプライベートにリリースするための新しい効率的なアルゴリズムを設計する。我々は,$k$の辺縁クエリを$n$の機能に対して計算する新しいアルゴリズムを導出する。
論文参考訳（メタデータ） (2024-06-07T12:07:16Z)
Fast Rates for Maximum Entropy Exploration [52.946307632704645]
エージェントが未知の環境下で活動し、報酬が得られない場合、強化学習(RL)における探索の課題に対処する。本研究では,最大エントロピー探索問題を2つの異なるタイプで検討する。訪問エントロピーには、$widetildemathcalO(H3S2A/varepsilon2)$ sample complexity を持つゲーム理論アルゴリズムを提案する。軌道エントロピーに対しては,次数$widetildemathcalO(mathrmpoly(S,)の複雑さのサンプルを持つ単純なアルゴリズムを提案する。
論文参考訳（メタデータ） (2023-03-14T16:51:14Z)
Nonlocality under Computational Assumptions [51.020610614131186]
相関の集合が非局所であるとは、空間的分離な当事者がランダム性を共有し、局所的な操作を実行することによって再現できないことである。ランダム性や量子時間計算によって再現できない局所的な(効率のよい)測定結果が存在することを示す。
論文参考訳（メタデータ） (2023-03-03T16:53:30Z)
Biased Random Access Codes [0.0]
ランダムアクセスコード(英: random access code、RAC)は、送信者が受信機によって復号される短いメッセージにランダムメッセージを符号化する通信タスクである。本稿では,古典的戦略と量子的戦略の両方に対して最適性能を数値的に評価するアルゴリズムを提案する。
論文参考訳（メタデータ） (2023-02-16T18:53:25Z)
Near Sample-Optimal Reduction-based Policy Learning for Average Reward MDP [58.13930707612128]
この研究は、平均報酬マルコフ決定過程(AMDP)における$varepsilon$-Optimal Policyを得る際のサンプルの複雑さを考察する。我々は、状態-作用対当たりの$widetilde O(H varepsilon-3 ln frac1delta)$サンプルを証明し、$H := sp(h*)$は任意の最適ポリシーのバイアスのスパンであり、$varepsilon$は精度、$delta$は失敗確率である。
論文参考訳（メタデータ） (2022-12-01T15:57:58Z)
Linear Contextual Bandits with Adversarial Corruptions [91.38793800392108]
本稿では,敵対的腐敗の存在下での線形文脈的包帯問題について検討する。逆汚染レベルに適応する分散認識アルゴリズムをC$で提案する。
論文参考訳（メタデータ） (2021-10-25T02:53:24Z)
PAC Mode Estimation using PPR Martingale Confidence Sequences [5.623190096715942]
離散分布 $mathcalP$ のモードを十分に高い確率で正確に同定する問題を考える。モード推定の一般化を提案し、$mathcalP$は$K geq 2$値を取ることができる。結果,PPR-MEと表される停止規則は,対数係数までのサンプル複雑性において最適である。
論文参考訳（メタデータ） (2021-09-10T18:11:38Z)

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