論文の概要: Improved Upper Bounds for Slicing the Hypercube

• arxiv url: http://arxiv.org/abs/2602.16807v1
• Date: Fri, 06 Feb 2026 17:52:13 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-23 12:01:13.70561
• Title: Improved Upper Bounds for Slicing the Hypercube
• Title（参考訳）: ハイパーキューブスライシングにおける上界の改善
• Authors: Duncan Soiffer, Nathaniel Itty, Christopher D. Rosin, Blake Bruell, Mason DiCicco, Gábor N. Sárközy, Ryan Offstein, Daniel Reichman,
• Abstract要約: 我々は、$S(n) leq lceil frac4n5 rceil$を証明しているが、$n$が5ドルという奇数の倍である場合を除いて、$S(n) leq frac4n5 +1$である。 また、$kn$超平面でスライスできる$Q_n$のエッジの最大数に関する新しい下界も得られる。
• 参考スコア（独自算出の注目度）: 2.285975776672996
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: A collection of hyperplanes $\mathcal{H}$ slices all edges of the $n$-dimensional hypercube $Q_n$ with vertex set $\{-1,1\}^n$ if, for every edge $e$ in the hypercube, there exists a hyperplane in $\mathcal{H}$ intersecting $e$ in its interior. Let $S(n)$ be the minimum number of hyperplanes needed to slice $Q_n$. We prove that $S(n) \leq \lceil \frac{4n}{5} \rceil$, except when $n$ is an odd multiple of $5$, in which case $S(n) \leq \frac{4n}{5} +1$. This improves upon the previously known upper bound of $S(n) \leq \lceil\frac{5n}{6} \rceil$ due to Paterson reported in 1971. We also obtain new lower bounds on the maximum number of edges in $Q_n$ that can be sliced using $k<n$ hyperplanes. We prove the improved upper bound on $S(n)$ by constructing $8$ hyperplanes slicing $Q_{10}$ aided by the recently introduced CPro1: an automatic tool that uses reasoning LLMs coupled with automated hyperparameter tuning to create search algorithms for the discovery of mathematical constructions.
• Abstract（参考訳）: ハイパープレーンの集合 $\mathcal{H}$ は、頂点集合 $\{-1,1\}^n$ で$n$-次元ハイパーキューブ $Q_n$ のすべての辺をスライスする。 S(n)$ を$Q_n$ をスライスするために必要な超平面の最小数とする。 S(n) \leq \lceil \frac{4n}{5} \rceil$は、$n$が5ドルの奇倍数である場合を除いて、$S(n) \leq \frac{4n}{5} +1$であることを示す。 これは、1971年にパターソンが報告したように、以前に知られていた$S(n) \leq \lceil\frac{5n}{6} \rceil$の上限を改善する。 また、$Q_n$ の辺の最大個数は $k<n$ の超平面でスライスできる。 我々は、最近導入されたCPro1によって支援された$Q_{10}$を8ドルの超平面にスライシングすることで、$S(n)$の上限を改良したことを証明した。

関連論文リスト

• Near-Optimal Convergence of Accelerated Gradient Methods under Generalized and $(L_0, L_1)$-Smoothness [57.93371273485736]
  我々は、最近提案された$ell$-smoothness条件$|nabla2f(x)|| le ellleft(||nabla f(x)||right),$$$L$-smoothnessと$(L_0,L_1)$-smoothnessを一般化する関数を持つ凸最適化問題の一階法について検討する。
  論文  参考訳（メタデータ） (2025-08-09T08:28:06Z)
• Lower Bounds for Greedy Teaching Set Constructions [12.186950360560145]
  我々は、小さな$k$に対してgreedyアルゴリズムの性能の低いバウンダリを証明した。 ほとんどの場合、我々の下界は小さな定数$c>0$に対して$k le lceil c d rceil$まで伸びる。
  論文  参考訳（メタデータ） (2025-05-06T06:30:01Z)
• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。 アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
  論文  参考訳（メタデータ） (2024-10-26T06:21:42Z)
• Tight Lower Bounds under Asymmetric High-Order Hölder Smoothness and Uniform Convexity [6.309677398331863]
  我々は最適性ギャップの観点から、$Omegaleft( left( fracHsigmaright)frac23(p+nu)$の最悪のオラクル複合体を確立する。 我々の結果は、この一般的な設定における対応する上界と一致する。
  論文  参考訳（メタデータ） (2024-09-16T23:17:33Z)
• $\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)
• (1,1)-Cluster Editing is Polynomial-time Solvable [0.0]
  a*: V(G)rightarrow 0,1,dots, a and $d*: V(G)rightarrow 0,1,dots, a and $d*: V(G)rightarrow 0,1,dots, a and $d*: V(G)rightarrow 0,1,dots, a and $d*: V(G)rightarrow 0,1,dots, a and $d*
  論文  参考訳（メタデータ） (2022-10-14T11:40:34Z)
• Algorithms for Discrepancy, Matchings, and Approximations: Fast, Simple, and Practical [1.2183405753834562]
  有限集合系 $(X,mathcal S)$ が与えられたとき、2色の $chi:Xto-1,1$ は数学的な S|chi(S)|$ において $max_S として定義される。 我々は、任意の$d>0$と$(X,mathcal S)$に対して、二重シャッター関数 $pi*(k)=O(kd)$ のランダム化アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-09-02T15:59:09Z)
• Near-Linear Time and Fixed-Parameter Tractable Algorithms for Tensor Decompositions [51.19236668224547]
  テンソルの低階近似について検討し,テンソルトレインとタッカー分解に着目した。 テンソル列車の分解には、小さなビクリテリアランクを持つビクリテリア$(1 + eps)$-approximationアルゴリズムと、O(q cdot nnz(A))$ランニングタイムを与える。 さらに、任意のグラフを持つテンソルネットワークにアルゴリズムを拡張します。
  論文  参考訳（メタデータ） (2022-07-15T11:55:09Z)
• Low-Rank Approximation with $1/\epsilon^{1/3}$ Matrix-Vector Products [58.05771390012827]
  我々は、任意のSchatten-$p$ノルムの下で、低ランク近似のためのクリロフ部分空間に基づく反復法について研究する。 我々の主な成果は、$tildeO(k/sqrtepsilon)$ matrix-vector productのみを使用するアルゴリズムである。
  論文  参考訳（メタデータ） (2022-02-10T16:10:41Z)
• On the Self-Penalization Phenomenon in Feature Selection [69.16452769334367]
  カーネル群に基づく暗黙の空間性誘導機構について述べる。 アプリケーションとしては、この疎結合誘導機構を使用して、特徴選択に一貫性のあるアルゴリズムを構築します。
  論文  参考訳（メタデータ） (2021-10-12T09:36:41Z)
• Linear Bandits on Uniformly Convex Sets [88.3673525964507]
  線形バンディットアルゴリズムはコンパクト凸作用集合上の $tildemathcalo(nsqrtt)$ pseudo-regret 境界を与える。 2種類の構造的仮定は、より良い擬似回帰境界をもたらす。
  論文  参考訳（メタデータ） (2021-03-10T07:33:03Z)
• Some convergent results for Backtracking Gradient Descent method on Banach spaces [0.0]
  bf Theorem.$X$をバナッハ空間とし、$f:Xrightarrow mathbbR$を$C2$関数とする。 $mathcalC$ を $f$ の臨界点の集合とする。
  論文  参考訳（メタデータ） (2020-01-16T12:49:42Z)

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

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