論文の概要: Information Loss Is All You Need: $TC^0$ Pseudorandomness from Worst-Case Lattices
- arxiv url: http://arxiv.org/abs/2611.05136v2
- Date: Thu, 05 Nov 2026 03:17:55 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-11-06 21:50:50.389906
- Title: Information Loss Is All You Need: $TC^0$ Pseudorandomness from Worst-Case Lattices
- Title（参考訳）: 情報損失がすべて:$TC^0$ Pseudorandomness from Worst-Case Lattices
- Abstract要約: 決定論的ラウンドリングは, パラメータが固定され, 所定のサンプル境界が存在しない, 量子最悪の格子硬さでこれを達成できることを示す。
これにより、最初の量子後弱擬似乱数関数が$TC0$のジョイント・キー・アンド・インプット・アセスメントを持つ。
また、雑音のない一様ランダムな例から学習サイズの2層ReLUネットワークの難しさを証明した。
- 参考スコア（独自算出の注目度）: 12.15064553632491
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Can deterministic information loss yield post-quantum pseudorandomness with $TC^0$ evaluation? We show that deterministic rounding achieves this under quantum worst-case lattice hardness, with fixed polynomial parameters and no predetermined sample bound. We introduce learning with algebraic rounding (LAR), which applies an explicit integer rounding map to blocks of secret-dependent linear measurements and encodes the result in a lattice quotient. For one fixed family with polynomially bounded modulus and dimensions, deterministic labels on exactly uniform, secret-independent public matrices are computationally indistinguishable from independent uniform labels for every polynomial number of classical random examples. Our classical reduction from Gaussian LWE, combined with the quantum worst-case reduction to LWE, bases LAR on GapSVP and SIVP over general lattices at approximation factor $\widetilde{O}(q)$, where $q$ is the modulus. The proof uses source-independent affine transport: public affine maps sampled independently of the hidden errors transport the Gaussian error law close to uniform on the rounding map's zero-label fiber while preserving exactly uniform public matrices. For every fixed inverse-polynomial accuracy, we give a polynomial-time sampler for the same public parameter family. This yields the first post-quantum weak pseudorandom function with joint key-and-input evaluation in $TC^0$, secure against uniform quantum polynomial-time distinguishers given any polynomial number of classical uniform random examples. We also prove hardness of learning polynomial-size two-hidden-layer ReLU networks from noiseless uniform random examples, even for quantum polynomial-time improper learners.
- Abstract（参考訳）: 決定論的情報損失は、$TC^0$評価による擬似ランダム性を生じるか?
決定論的ラウンドリングは, 定数が固定され, 所定のサンプル境界が存在しない, 量子最悪の格子硬さでこれを達成できることを示す。
秘密依存線形測定のブロックに明示的な整数丸め写像を適用し、格子商で結果を符号化する代数的丸め法(LAR)を導入する。
多項式有界なモジュラーと次元を持つ1つの固定族に対して、正に均一で秘密非独立な公共行列上の決定論的ラベルは、古典的乱例のすべての多項式数に対して独立な均一なラベルとは計算的に区別できない。
ガウス LWE からの古典的な還元は、量子最悪の LWE への還元と相まって、GapSVP 上の LAR と SIVP を近似係数 $\widetilde{O}(q)$ の一般格子上の SIVP の基底とし、$q$ はモジュラーである。
公開アフィン写像は隠れエラーとは独立にサンプリングされ、丸め写像のゼロラベルファイバー上の均一に近いガウス誤差法則を輸送し、完全に均一な公共行列を保存する。
各固定逆多項式精度に対して、同じ公共パラメータ群に対して多項式時間サンプリング器を与える。
これにより、量子後弱擬似ランダム関数が$TC^0$のジョイントキー・アンド・インプット評価を持ち、古典的な一様ランダムな例の多項式数が与えられた均一な量子多項式時間差分器に対して確保される。
また、量子多項式時間不適切な学習者であっても、雑音のない一様ランダムな例から多項式サイズの2層ReLUネットワークを学習することが困難であることを示す。
関連論文リスト
- Strictly Replicable Realizable Learning: Unknown Marginals, Finite-Class Interpolation, and the Cost of Shared Randomness [0.0]
本研究では,未知の,未知の,未知の,未知の事例の残差に基づく実存可能なブール学習について検討する。
決定論的学習、任意の有限類に対する極小$$レギュレーション、VC 1 の有限類に対するすべての濃度-再現性レギュレーションを特徴付ける。
論文 参考訳（メタデータ） (2026-10-18T05:17:14Z) - Verifiable quantum advantage based on polynomials with planted structures [13.376362080307027]
検証可能なシミュレーションシークレットのアイデアを,検証可能な優位性のために開発する。
検証者はシミュレーション秘密を使って、クロスエントロピーテストを評価することができる。
論文 参考訳（メタデータ） (2026-09-30T15:08:28Z) - Sample Complexity of Multicalibration for Multilevel Properties [52.27687531970317]
我々は、前のプロパティが固定されたときに各プロパティが識別可能な$k$プロパティの列に対する多重校正について検討する。
多対数的に多くの二元群が存在するにもかかわらず、多重校正誤差$varepsilon$を達成するには$widetilde(varepsilon-(k+2))$サンプルが必要である。
論文 参考訳（メタデータ） (2026-08-04T23:38:54Z) - Exponential Reduction of Mesh Dependence in Quantum Estimation of Parabolic PDE Observables [3.3636842548621275]
線形および二次可観測物を推定し、測定前に回路内部に粗いキャンセリングを配置する量子PDEアルゴリズムを開発した。
また、1次元のエネルギー直交ダイアド中間点の詳細に基づく非フーリエ実現を与える。
論文 参考訳（メタデータ） (2026-07-20T16:09:24Z) - Is Spurious Correlation Removal Always Learnable? [56.28155520961125]
不変学習は、構造が統計的に識別可能であっても失敗することがある。
ブラックボックスサンプリング可能な教師付きスパースリカバリプリミティブの下では、実証可能な多次元環境が存在する。
合成および実際のデータセットは、予測されたギャップと遷移を示し、単純な多様性診断を動機付ける。
論文 参考訳（メタデータ） (2026-06-11T05:49:43Z) - Regularized Online RLHF with Generalized Bilinear Preferences [68.44113000390544]
一般的な嗜好を伴う文脈的オンラインRLHFの問題を考える。
一般化された双線形選好モデルを用いて、低ランクなスキュー対称行列による選好を捉える。
グリーディポリシーの双対ギャップは推定誤差の正方形によって有界であることを示す。
論文 参考訳（メタデータ） (2026-02-26T15:27:53Z) - Quantum Advantage via Solving Multivariate Polynomials [21.099298465042583]
3次関数はランダムなオラクルをインスタンス化して非相対化量子優位を得るのに十分であることを示す。
p_i(x_ldots,x_n)=y_i_iin [m]$ for $mn$ over $mathbbF$。
論文 参考訳（メタデータ） (2025-09-08T23:19:20Z) - Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
近年の研究では、再生カーネルヒルベルト空間(RKHS)がニューラルネットワークによる関数のモデル化に適した空間ではないことが示されている。
本稿では,有界ノルムを持つオーバーパラメータ化された2層ニューラルネットワークに適した関数空間について検討する。
論文 参考訳（メタデータ） (2024-04-29T15:04:07Z) - Influence in Completely Bounded Block-multilinear Forms and Classical
Simulation of Quantum Algorithms [3.9156637371363874]
Aaronson-Ambainis予想を証明する(Theory of Computing '14)
すべての完全有界次数-$d$ブロック-多重線型形式において、常に影響が少なくとも1/mathrmpoly(d)$の変数が存在する。
我々は、量子アルゴリズムの特定のクラスに対する効率的な古典的ほぼすべてのところのシミュレーションを得る。
論文 参考訳（メタデータ） (2022-03-01T03:42:24Z) - Quantum Communication Complexity of Distribution Testing [114.31181206328276]
2人のプレーヤーが1つのディストリビューションから$t$のサンプルを受け取ります。
目標は、2つの分布が等しいか、または$epsilon$-far であるかどうかを決定することである。
この問題の量子通信複雑性が$tildeO$(tepsilon2)$ qubitsであることを示す。
論文 参考訳（メタデータ） (2020-06-26T09:05:58Z) - Robustly Learning any Clusterable Mixture of Gaussians [55.41573600814391]
本研究では,高次元ガウス混合系の対向ロバスト条件下での効率的な学習性について検討する。
理論的に最適に近い誤り証明である$tildeO(epsilon)$の情報を、$epsilon$-corrupted $k$-mixtureで学習するアルゴリズムを提供する。
我々の主な技術的貢献は、ガウス混合系からの新しい頑健な識別可能性証明クラスターであり、これは正方形の定度証明システムによって捉えることができる。
論文 参考訳（メタデータ） (2020-05-13T16:44:12Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。