論文の概要: Cell-Probe Lower Bounds via Semi-Random CSP Refutation: Simplified and the Odd-Locality Case
- arxiv url: http://arxiv.org/abs/2507.22265v1
- Date: Tue, 29 Jul 2025 22:33:09 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-07-31 16:14:17.889553
- Title: Cell-Probe Lower Bounds via Semi-Random CSP Refutation: Simplified and the Odd-Locality Case
- Title（参考訳）: 半ランダムCSP難治化による細胞プローブ下境界の簡易化とオッド局所性例
- Authors: Venkatesan Guruswami, Xin Lyu, Weiqiang Yuan,
- Abstract要約: 入力を実質的に拡張するマルチ出力の定数深度回路の場合、その出力は十分な独立性を持つ分布からサンプリングされた文字列から非常に遠い可能性が示されている。
これにより、$mathsfNC0$回路のセル-プローブローバウンドとレンジ回避アルゴリズムへの応用が可能になる。
- 参考スコア（独自算出の注目度）: 22.29614516455028
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: A recent work (Korten, Pitassi, and Impagliazzo, FOCS 2025) established an insightful connection between static data structure lower bounds, range avoidance of $\text{NC}^0$ circuits, and the refutation of pseudorandom CSP instances, leading to improvements to some longstanding lower bounds in the cell-probe/bit-probe models. Here, we improve these lower bounds in certain cases via a more streamlined reduction to XOR refutation, coupled with handling the odd-arity case. Our result can be viewed as a complete derandomization of the state-of-the-art semi-random $k$-XOR refutation analysis (Guruswami, Kothari and Manohar, STOC 2022, Hsieh, Kothari and Mohanty, SODA 2023), which complements the derandomization of the even-arity case obtained by Korten et al. As our main technical statement, we show that for any multi-output constant-depth circuit that substantially stretches its input, its output is very likely far from strings sampled from distributions with sufficient independence, and further this can be efficiently certified. Via suitable shifts in perspectives, this gives applications to cell-probe lower bounds and range avoidance algorithms for $\mathsf{NC}^0$ circuits.
- Abstract（参考訳）: 最近の研究(Korten, Pitassi, Impagliazzo, FOCS 2025)では、静的データ構造の下限、$\text{NC}^0$回路の範囲回避、擬似ランダムCSPインスタンスの難読化といった洞察に富んだ接続が確立され、セルプローブ/ビットプローブモデルにおける長期の下位境界の改善につながった。
ここでは、XORの難燃度をより簡潔に低減し、奇数のケースを扱えるようにすることで、特定の場合のこれらの下限を改善する。
我々の結果は、Kortenらによって得られた均等性ケースのデランドマイズを補完する最先端の半ランダム$k$-XOR難燃分析(Guruswami, Kothari and Manohar, STOC 2022, Hsieh, Kothari and Mohanty, SODA 2023)の完全なデランドマイズと見なすことができる。
パースペクティブの適切なシフトにより、$\mathsf{NC}^0$回路に対するセルプローブ下界とレンジ回避アルゴリズムへの応用が提供される。
関連論文リスト
- Convergent Privacy Loss of Noisy-SGD without Convexity and Smoothness [16.303040664382138]
有界領域上の隠れ状態雑音-SGDアルゴリズムの差分プライバシー(DP)保証について検討する。
我々は非滑らかな非滑らかな損失に対して収束R'enyi DPを証明した。
我々はまた、滑らかな凸損失に対する最先端の結果と比較して、厳格に優れたプライバシー境界を提供する。
論文 参考訳（メタデータ） (2024-10-01T20:52:08Z) - Nystr\"om Kernel Mean Embeddings [92.10208929236826]
Nystr"om法に基づく効率的な近似手法を提案する。
サブサンプルサイズの条件は標準の$n-1/2$レートを得るのに十分である。
本稿では,この結果の最大誤差と二次規則の近似への応用について論じる。
論文 参考訳（メタデータ） (2022-01-31T08:26:06Z) - Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and
Beyond [63.59034509960994]
シャッフルに基づく変種(ミニバッチと局所ランダムリシャッフル)について検討する。
ポリアック・ロジャシエヴィチ条件を満たす滑らかな函数に対して、これらのシャッフル型不変量(英語版)(shuffling-based variants)がそれらの置換式よりも早く収束することを示す収束境界を得る。
我々は, 同期シャッフル法と呼ばれるアルゴリズムの修正を提案し, ほぼ均一な条件下では, 下界よりも収束速度が速くなった。
論文 参考訳（メタデータ） (2021-10-20T02:25:25Z) - A Unifying Theory of Thompson Sampling for Continuous Risk-Averse
Bandits [91.3755431537592]
本稿では,多腕バンディット問題に対するリスク-逆トンプソンサンプリングアルゴリズムの解析を統一する。
大規模偏差理論における収縮原理を用いることで、連続リスク汎関数に対する新しい濃度境界が証明される。
リスク関数の幅広いクラスと「ニセ」関数が連続性条件を満たすことを示す。
論文 参考訳（メタデータ） (2021-08-25T17:09:01Z) - Lattice partition recovery with dyadic CART [79.96359947166592]
我々は、$d$次元格子上の加法ガウス雑音によって破損したピースワイド定値信号について検討する。
この形式のデータは、多くのアプリケーションで自然に発生し、統計処理や信号処理の文献において、信号の検出やテスト、ノイズの除去、推定といったタスクが広く研究されている。
本稿では,未知の信号の一貫性領域によって誘導される格子の分割を推定する,分割回復の問題について考察する。
我々は、DCARTベースの手順が、下位分割を$sigma2 k*の順序で一貫して推定することを証明した。
論文 参考訳（メタデータ） (2021-05-27T23:41:01Z) - Robust Uncertainty Bounds in Reproducing Kernel Hilbert Spaces: A Convex
Optimization Approach [9.462535418331615]
サンプル外境界は、見当たらない入力位置で確立できることが知られている。
有限サンプルの不確実性境界の密接な計算は、パラメトリック制約付き線形プログラムを解くのにどのように役立つかを示す。
論文 参考訳（メタデータ） (2021-04-19T19:27:52Z) - Improved device-independent randomness expansion rates using two sided
randomness [3.4376560669160394]
デバイスに依存しないランダム性拡張プロトコルは、初期乱数列を取り、より長い乱数列を生成することを目的としている。
両面のランダム性によって得られる改善の可能性を検討する。
また、入力ランダム性を再利用する修正プロトコルについても検討する。
論文 参考訳（メタデータ） (2021-03-12T19:49:17Z) - On the Almost Sure Convergence of Stochastic Gradient Descent in
Non-Convex Problems [75.58134963501094]
本稿では,勾配降下(SGD)の軌跡を解析する。
我々はSGDが厳格なステップサイズポリシーのために1ドルでサドルポイント/マニフォールドを避けることを示す。
論文 参考訳（メタデータ） (2020-06-19T14:11:26Z) - Learning Halfspaces with Tsybakov Noise [50.659479930171585]
テュバコフ雑音の存在下でのハーフスペースの学習可能性について検討する。
真半空間に関して誤分類誤差$epsilon$を達成するアルゴリズムを与える。
論文 参考訳（メタデータ） (2020-06-11T14:25:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。