論文の概要: Optimizing Explicit Unit-Distance Lower-Bound Certificates

• arxiv url: http://arxiv.org/abs/2606.03419v1
• Date: Tue, 02 Jun 2026 10:05:23 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-03 22:00:04.923924
• Title: Optimizing Explicit Unit-Distance Lower-Bound Certificates
• Title（参考訳）: 明示的単位距離下界証明書の最適化
• Abstract要約: 2026年のエルドスの単位距離予想とサウィンの明示的な量的洗練の反証は、最大数$u(n)$が任意の大きな距離に対して$n1+varilon$を超えることを示している。 本稿では,有限パラメータ選択タスクを非線形整数計画問題の変種として定式化する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The 2026 disproof of Erdős's unit-distance conjecture and Sawin's subsequent explicit quantitative refinement show that the maximum number $u(n)$ of unit distances among $n$ planar points can exceed $n^{1+\varepsilon}$ for a fixed positive $\varepsilon$. Sawin's explicit bound gives more than $n^{1.014}$ unit distances for arbitrarily large $n$ and exposes finite parameters whose choice is not fully optimized. This report formulates the finite parameter-selection task as a variant of a nonlinear integer programming problem and proposes an open-source Python verification pipeline, first validated by reproducing Sawin's published parameter choice and then applied to computationally improved certificates. The main computational contribution is an integer optimization and checking procedure for the sets of primes $T$ and $S_Q$, the integer multiplicities $k(p)$, and a rationally encoded real parameter $R$. The optimization pipelines are intentionally lightweight and replicable on standard hardware: we propose a deterministic greedy construction heuristic, a Tailored Integer Evolution Strategy with repair operators for number-theoretic feasibility, and a two-parent discrete-recombination variant. Four certificate levels are compared: Sawin's published example with $δ=0.0141144286784982\ldots$, a greedy optimization certificate with $δ=0.0151718056372133\ldots$, a Tailored Integer Evolution Strategy certificate with rational $R=6672416/100000$ and $δ=0.0152616610684193\ldots$, and a Tailored Integer Evolution Strategy with discrete recombination, again with $R=6672416/100000$, giving $δ=0.0152628688170072\ldots$. Consequently, subject to Sawin's explicit criterion being applied exactly as cited, the best current certificate supports the cautious clean statement $u(n)>n^{1.0152}$ for arbitrarily large $n$.
• Abstract（参考訳）: 2026年のエルデシュの単位距離予想と、サウィンのその後の明示的な量的洗練は、固定正の$\varepsilon$に対して、$n$平面点の間の単位距離の最大数$u(n)$が$n^{1+\varepsilon}$を超えることを示した。 サウィンの明示的な境界は、任意の大きさの$n$に対して$n^{1.014}$単位距離を与え、完全に最適化されていない有限パラメータを公開する。 本報告では、有限パラメータ選択タスクを非線形整数計画問題の変種として定式化し、まずサウィンのパラメータ選択を再現して検証したオープンソースのPython検証パイプラインを提案し、その後、計算的に改善された証明書に適用する。 主な計算貢献は、素数の集合に対して$T$と$S_Q$、整数乗法$k(p)$、有理的に符号化された実パラメータ$R$に対する整数最適化とチェック手順である。 最適化パイプラインは、標準ハードウェア上では意図的に軽量で複製可能であり、決定論的欲求的構成ヒューリスティック、数論的実現性のための修理演算子を備えたTalored Integer Evolution Strategy、および2対の離散再結合変種を提案する。 Sawinは、$δ=0.0141144286784982\ldots$、$δ=0.0151718056372133\ldots$、有理な$R=6672416/100000$、$δ=0.01526616684193\ldots$、$R=6672416/100000$、さらに$R=0.0152628688170072\ldots$の4つの証明レベルを公表している。 したがって、サウィンの明示的な基準は、正確に引用されたように適用され、最高の現在の証明書は、任意に大きい$n$に対して、慎重なクリーンステートメント $u(n)>n^{1.0152} をサポートする。

関連論文リスト

• A Sharp Barrier for Consistent Submodular Maximization: Any Improvement over $2-\sqrt{2}$ Entails Exponential Queries or Linear Recourse [50.69285844345291]
  我々は、要素が時間とともに到着する際のソリューションの品質と安定性のトレードオフについて研究する。 我々のアルゴリズムは,有理オラクル$を$O(varepsilon-1)$recourseで実装し,そのアルゴリズムから普遍価格証明書の存在を分離する。
  論文  参考訳（メタデータ） (2026-09-09T10:13:43Z)
• The Condition-Number Barrier in Sparse Least Squares [77.64108812086542]
  AxiotisとSviridenkoは[AS21]において、凸最適化における制限条件数への線形依存はスパース時間アルゴリズムでは改善できないと推測した。 我々は、最小二乗目的に対する予想下界を確立し、ランダム化された完全体積小セット展開仮説に基づく条件付けを行う。
  論文  参考訳（メタデータ） (2026-08-03T17:57:01Z)
• Certificate-Guided Pruning for Stochastic Lipschitz Optimization [6.908972852063454]
  雑音評価の下で,リプシッツ関数のブラックボックス最適化について検討した。 既存の適応的な離散化手法は、暗黙的に最適領域を避けるが、最適性や測定可能な進捗保証の明確な証明書は提供していない。 本稿では、アダプティブテキストbf-Guided Pruning (CGP)を導入し、信頼調整リプシッツエンベロープによる潜在的最適点の集合A_t$を明示的に維持する。
  論文  参考訳（メタデータ） (2026-01-28T04:02:22Z)
• Parameter-free Algorithms for the Stochastically Extended Adversarial Model [59.81852138768642]
  拡張逆数(SEA)モデルの既存のアプローチは、ドメインの直径$D$や損失関数のリプシッツ定数$G$といった問題固有のパラメータの事前知識を必要とする。 パラメータを不要にするためにOptimistic Online Newton Step (OONS) アルゴリズムを利用するパラメータフリー手法を開発した。
  論文  参考訳（メタデータ） (2025-10-06T10:53:37Z)
• Revisiting Step-Size Assumptions in Stochastic Approximation [1.3654846342364308]
  この仮定は、収束とより微細な結果には必要ないことが初めて示される。 標準アルゴリズムおよびPolyakとRuppertの平均化手法を用いて得られた推定値に対して収束率を求める。 数値実験の結果,乗法雑音とマルコフ記憶の組み合わせにより,$beta_theta$が大きくなる可能性が示唆された。
  論文  参考訳（メタデータ） (2024-05-28T05:11:05Z)
• Efficient, direct compilation of SU(N) operations into SNAP & Displacement gates [0.0]
  Map $Phi$は、$d$次元のユニタリを直接SNAPと変位ゲートのシーケンスにコンパイルする機能を提供する。 計算回路上の誤差は各回転を$m$$theta/m$回転に分割することで任意に小さくすることができる。
  論文  参考訳（メタデータ） (2023-07-21T20:58:17Z)
• Tight Bounds for $\gamma$-Regret via the Decision-Estimation Coefficient [88.86699022151598]
  任意の構造化バンディット問題に対する$gamma$-regretの統計的特徴を与える。 この$gamma$-regretは、関数クラス$mathcalF$上の構造化バンディット問題に現れる。
  論文  参考訳（メタデータ） (2023-03-06T17:54:33Z)
• Beyond Moments: Robustly Learning Affine Transformations with Asymptotically Optimal Error [8.615625517708324]
  サンプルから標準ハイパーキューブの未知アフィン変換を学習するためのリアルタイムアルゴリズムを提案する。 本アルゴリズムは,証明書の要求が満たされない場合に,未知アフィン変換の推定を反復的に改善する手法に基づいている。
  論文  参考訳（メタデータ） (2023-02-23T19:13:30Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• Approximate Function Evaluation via Multi-Armed Bandits [51.146684847667125]
  既知の滑らかな関数 $f$ の値を未知の点 $boldsymbolmu in mathbbRn$ で推定する問題について検討する。 我々は、各座標の重要性に応じてサンプルを学習するインスタンス適応アルゴリズムを設計し、少なくとも1-delta$の確率で$epsilon$の正確な推定値である$f(boldsymbolmu)$を返す。
  論文  参考訳（メタデータ） (2022-03-18T18:50:52Z)
• TURF: A Two-factor, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
  最も強力で成功したモダリティの1つは、全ての分布を$ell$距離に近似し、基本的に最も近い$t$-piece次数-$d_$の少なくとも1倍大きい。 本稿では,この数値をほぼ最適に推定する手法を提案する。
  論文  参考訳（メタデータ） (2022-02-15T03:49:28Z)
• Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
  我々は,バンディットフィードバックを用いてオンライン学習を学習する。 learnerは、コスト/リワード関数が"pseudo-1d"構造を許可するゼロ次オラクルのみにアクセスできる。 我々は、$T$がラウンドの数である任意のアルゴリズムの後悔のために$min(sqrtdT、T3/4)$の下限を示しています。 ランダム化オンライングラデーション下降とカーネル化指数重み法を組み合わせた新しいアルゴリズムsbcalgを提案し,疑似-1d構造を効果的に活用する。
  論文  参考訳（メタデータ） (2021-02-15T08:16:51Z)
• High-Order Oracle Complexity of Smooth and Strongly Convex Optimization [31.714928102950584]
  非常に滑らかな (Lipschitz $k$-thorder derivative) 関数と強い凸関数を$k$-thorder Oracleへの呼び出しによって最適化する複雑性を考える。 我々は、関数を正確に$epsilon$まで最適化するために、固定された$k$で最悪の場合のオラクルの複雑さが$leftの順序にあることを証明している。
  論文  参考訳（メタデータ） (2020-10-13T19:18:15Z)
• 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)
• Convergence of Sparse Variational Inference in Gaussian Processes Regression [29.636483122130027]
  計算コストが$mathcalO(log N)2D(log N)2)$の手法を推論に利用できることを示す。
  論文  参考訳（メタデータ） (2020-08-01T19:23:34Z)
• Curse of Dimensionality on Randomized Smoothing for Certifiable Robustness [151.67113334248464]
  我々は、他の攻撃モデルに対してスムースな手法を拡張することは困難であることを示す。 我々はCIFARに関する実験結果を示し,その理論を検証した。
  論文  参考訳（メタデータ） (2020-02-08T22:02:14Z)

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

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