論文の概要: Tiny Suffix Arrays

• arxiv url: http://arxiv.org/abs/2610.35543v1
• Date: Mon, 26 Oct 2026 14:53:37 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-27 22:27:14.039679
• Title: Tiny Suffix Arrays
• Title（参考訳）: Tiny Suffix Arrays
• Abstract要約: 長さ$n$のテキスト上の接尾辞配列と逆接尾辞配列クエリは、$widetildeO(3)$時間で答えられる。
• 参考スコア（独自算出の注目度）: 0.12691047660244334
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Suffix array and inverse suffix array queries on a text of length $n$ can be answered in $\widetilde{O}(τ^3)$ time using an auxiliary data structure occupying $O(n/τ)$ words, for any $τ\in [1,n]$.
• Abstract（参考訳）: 長さ$n$のテキスト上の接尾辞配列と逆接尾辞配列クエリは、$O(n/τ)$ワードを占有する補助データ構造を用いて$\widetilde{O}(τ^3)$ timeで答えることができる。

関連論文リスト

• Min-Max Optimization Requires Exponentially Many Queries [71.85811744604827]
  非min-nonconcave 関数 $f$ $[0,1] のクエリ複雑性。 f$ へのクエリとその勾配点が 1 ord$ で指数関数的な点を成さなければならないことを示す。
  論文  参考訳（メタデータ） (2026-05-13T17:34:24Z)
• Fast and Optimal Differentially Private Frequent-Substring Mining [2.451701057085567]
  ユーザ分散文字列のデータセットが$n$で、各長さが$ell$である場合、重要な問題は、すべての頻繁な呼び出しを識別する方法である。 我々は,空間複雑性を低減しつつ,ほぼ最適な誤差保証を保った新しい$varepsilon$-differentially privateアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2026-03-10T04:04:52Z)
• PREM: Privately Answering Statistical Queries with Relative Error [91.98332694700046]
  合成データを生成する新しいフレームワークである$mathsfPREM$(Private Relative Error Multiplicative weight update)を紹介します。 我々はアルゴリズムをほぼ一致する下界で補完する。
  論文  参考訳（メタデータ） (2025-02-20T18:32:02Z)
• On Differentially Private String Distances [12.852131074558057]
  基本的なデータ構造タスクは、データベース内のすべての文字列で、与えられたクエリのBin 0,1n$間の距離を見積もることである。 本稿では,このようなタスクに対して,ハミングと編集距離に着目した差分プライベート(DP)データ構造を提案する。 そこで我々は,ビットフリップ法としてランダム化応答手法の新たな適応により,これらの結果を得た。
  論文  参考訳（メタデータ） (2024-11-08T18:10:07Z)
• LevAttention: Time, Space, and Streaming Efficient Algorithm for Heavy Attentions [54.54897832889028]
  任意の$K$に対して、$n$とは独立に「普遍集合」$Uサブセット[n]$が存在し、任意の$Q$と任意の行$i$に対して、大きな注目スコアが$A_i,j$ in row $i$ of $A$は全て$jin U$を持つことを示す。 我々は、視覚変換器のスキームの利点を実証的に示し、トレーニング中に我々の普遍的なセットを使用する新しいモデルのトレーニング方法を示した。
  論文  参考訳（メタデータ） (2024-10-07T19:47:13Z)
• When Variable-Length Codes Meet the Field of Error Detection [0.0]
  citeJK97,N21の精神では、可変長符号の誤り検出補正能力は$tau_d,k$以上の条件で表現できる。 所定の正規コードに対して、それらの条件が決定可能であるかどうかを検討する。
  論文  参考訳（メタデータ） (2022-08-31T08:14:28Z)
• 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)
• Learning low-degree functions from a logarithmic number of random queries [77.34726150561087]
  任意の整数 $ninmathbbN$, $din1,ldots,n$ および任意の $varepsilon,deltain(0,1)$ に対して、有界関数 $f:-1,1nto[-1,1]$ に対して、少なくとも$d$ の次数を学ぶことができる。
  論文  参考訳（メタデータ） (2021-09-21T13:19:04Z)
• Gray Cycles of Maximum Length Related to k-Character Substitutions [0.0]
  単語のバイナリ関係が与えられたとき、$tau$-Gray サイクルを有限言語 $X$ 上で定義し、置換 $left(w_[i]right)_0le ile |X|-1$ of $X$ とする。 アルファベットの基数と引数$n$のすべてのケースに対して有界な$lambda(n)$を計算する。
  論文  参考訳（メタデータ） (2021-08-31T07:49:15Z)
• Learning a Latent Simplex in Input-Sparsity Time [58.30321592603066]
  我々は、$AinmathbbRdtimes n$へのアクセスを考えると、潜入$k$-vertex simplex $KsubsetmathbbRdtimes n$を学習する問題を考える。 実行時間における$k$への依存は、トップ$k$特異値の質量が$a$であるという自然な仮定から不要であることを示す。
  論文  参考訳（メタデータ） (2021-05-17T16:40:48Z)
• On Computing Stable Extensions of Abstract Argumentation Frameworks [1.1251593386108185]
  textitabstract argumentation framework (sc af) は有向グラフ $(A,R)$ であり、$A$ はtextitabstract arguments の集合であり、$Rsubseteq A times A$ は textit attack relation である。 与えられた sc における全ての安定な拡張をリストアップするための、既知のバックトラックアルゴリズムの徹底的な形式的検証を示す。
  論文  参考訳（メタデータ） (2020-11-03T05:38:52Z)

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

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