論文の概要: Towards EXPTIME One Way Functions: Bloom Filters, Succinct Graphs, Cliques, & Self Masking

• arxiv url: http://arxiv.org/abs/2508.01649v1
• Date: Sun, 03 Aug 2025 08:16:35 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-08-12 14:02:02.549532
• Title: Towards EXPTIME One Way Functions: Bloom Filters, Succinct Graphs, Cliques, & Self Masking
• Title（参考訳）: EXPTIMEのワンウェイ機能に向けて: ブルームフィルタ, アクセントグラフ, 斜め, セルフマスキング
• Authors: Shlomi Dolev,
• Abstract要約: n 個のノードのグラフを検討し、長さ 2 log3 n ビットのブルームフィルタを使用する。 i と j の間の端点 i と j は、i と j 上のハッシュ関数に従ってブルームフィルタの特定のビットを反転させる。 ブルームフィルタは、x と y にハッシュ関数を適用することで選択された全てのビットがブルームフィルタに斜めのエッジを巻き込むためにオンになったような、他のエッジ、すなわち x y のあるエッジの存在を暗示する。
• 参考スコア（独自算出の注目度）: 7.23389716633927
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Consider graphs of n nodes, and use a Bloom filter of length 2 log3 n bits. An edge between nodes i and j, with i < j, turns on a certain bit of the Bloom filter according to a hash function on i and j. Pick a set of log n nodes and turn on all the bits of the Bloom filter required for these log n nodes to form a clique. As a result, the Bloom filter implies the existence of certain other edges, those edges (x, y), with x < y, such that all the bits selected by applying the hash functions to x and y happen to have been turned on due to hashing the clique edges into the Bloom filter. Constructing the graph consisting of the clique-selected edges and those edges mapped to the turned-on bits of the Bloom filter can be performed in polynomial time in n. Choosing a large enough polylogarithmic in n Bloom filter yields that the graph has only one clique of size log n, the planted clique. When the hash function is black-boxed, finding that clique is intractable and, therefore, inverting the function that maps log n nodes to a graph is not (likely to be) possible in polynomial time.
• Abstract（参考訳）: n 個のノードのグラフを検討し、長さ 2 log3 n ビットのブルームフィルタを使用する。 i < j のノード i と j の間のエッジは、i と j のハッシュ関数に従って、ブルームフィルタの特定のビットをオンにする。 ログnノードのセットを選択して、これらのログnノードがcliqueを形成するために必要なブルームフィルタのすべてのビットをオンにする。 結果として、ブルームフィルタは、これらのエッジ (x, y) と x < y の存在を意味しており、したがって、ハッシュ関数を x と y に適用することによって選択された全てのビットは、クリッドエッジをブルームフィルタにハッシュすることで、たまたまオンになった。 クリプト選択されたエッジとブルームフィルタのターンオンビットにマッピングされたエッジからなるグラフを構成することは、n の多項式時間で行うことができる。 n 個のブルームフィルタで十分大きな多元性を選択すると、グラフは1つの大きさの丸太 n の傾きしか持たない。 ハッシュ関数がブラックボックス化されているとき、clique は難解であり、従って n 個のノードをグラフにマッピングする関数を逆転することは多項式時間では不可能である。

関連論文リスト

• Partition-wise Graph Filtering: A Unified Perspective Through the Lens of Graph Coarsening [15.198274855557132]
  本稿ではCPF(Coarsening-guided Partition-wise Filtering)を紹介する。 CPFはノード分割でフィルタリングを実行することで革新する。 CPFの各相について詳細な解析を行い、他のパラダイムよりも優れていることを示す。
  論文  参考訳（メタデータ） (2025-05-20T07:30:45Z)
• Sublinear Space Graph Algorithms in the Continual Release Model [48.65946341463292]
  我々は,非プライベートなストリーミングと静的アルゴリズムからスペーシフィケーション手法を新たに利用して,サブ線形空間における新たな結果,連続的なリリース設定を実現する。 これには、最も高密度な部分グラフのためのアルゴリズム、最大マッチング、および最初の連続リリース$k$-core分解アルゴリズムが含まれる。
  論文  参考訳（メタデータ） (2024-07-24T20:15:07Z)
• PolyFormer: Scalable Node-wise Filters via Polynomial Graph Transformer [22.287960384629585]
  本稿では,スケーラブルなノードワイドフィルタであるPolyAttnを提案する。 提案手法は任意のノードワイドフィルタの学習に優れ、ホモ親和性グラフとヘテロ親和性グラフの両方において優れた性能を示す。
  論文  参考訳（メタデータ） (2024-07-19T17:01:41Z)
• Graph Parsing Networks [64.5041886737007]
  本稿では,効率的なグラフ解析アルゴリズムを提案する。 結果として得られるグラフパーシングネットワーク(GPN)は、個々のグラフに対してパーソナライズされたプーリング構造を適応的に学習する。
  論文  参考訳（メタデータ） (2024-02-22T09:08:36Z)
• Careful Selection and Thoughtful Discarding: Graph Explicit Pooling Utilizing Discarded Nodes [53.08068729187698]
  本稿では,ノードと最終表現ベクトルの関係を明示的に活用してノードを選択するグラフ明示プール法を提案する。 提案手法の有効性を検証するため,12種類の広く使用されているデータセットを対象とした総合的な実験を行った。
  論文  参考訳（メタデータ） (2023-11-21T14:44:51Z)
• Online Filtering over Expanding Graphs [14.84852576248587]
  本稿では,オンライン機械学習の原理に基づいて,フィルタのオンライン更新を提案する。 受信ノードにおける信号に対する手法の性能を示す。 これらの発見は、グラフの拡張よりも効率的なフィルタリングの基礎を築いた。
  論文  参考訳（メタデータ） (2023-01-17T14:07:52Z)
• Learning Optimal Graph Filters for Clustering of Attributed Graphs [20.810096547938166]
  多くの現実世界のシステムは、システム内の異なるエンティティがノードによって表現され、エッジによって相互作用するグラフとして表現することができる。 グラフィカルな構造を持つ大規模なデータセットを研究する上で重要なタスクはグラフクラスタリングである。 本稿では,FIR(Finite Impulse Response)およびARMA(Autoregressive moving Average)グラフフィルタのパラメータをクラスタリングに最適化したグラフ信号処理手法を提案する。
  論文  参考訳（メタデータ） (2022-11-09T01:49:23Z)
• Daisy Bloom Filters [10.428888893980739]
  フィルター(英: filter)とは、ある宇宙から与えられた要素のセット$S$(可算集合)の近似を保存するために広く用いられるデータ構造である。 ブルームフィルタを使用する利点は、いくつかの偽陽性が許容されるとき、空間使用量が$S$を正確に保存するために必要なものよりも小さくなることである。 Bloom filter は $textitDaisy Bloom filter$ と呼ばれ、操作を高速に実行し、標準の Bloom filter よりもはるかに少ないスペースを使用する。
  論文  参考訳（メタデータ） (2022-05-30T07:22:24Z)
• Beyond Low-pass Filtering: Graph Convolutional Networks with Automatic Filtering [61.315598419655224]
  グラフ信号の全スペクトルをキャプチャする自動グラフ畳み込みネットワーク(AutoGCN)を提案する。 グラフスペクトル理論に基づいているが、私たちのAutoGCNも空間に局在しており、空間形式を持っている。
  論文  参考訳（メタデータ） (2021-07-10T04:11:25Z)
• Message Passing in Graph Convolution Networks via Adaptive Filter Banks [81.12823274576274]
  我々は BankGCN と呼ばれる新しいグラフ畳み込み演算子を提案する。 グラフ上のマルチチャネル信号をサブスペースに分解し、各サブスペース内の特定の情報を適応フィルタで処理する。 ベンチマークグラフデータセットの集合におけるグラフ分類における優れたパフォーマンスを実現する。
  論文  参考訳（メタデータ） (2021-06-18T04:23:34Z)
• Seeing All From a Few: Nodes Selection Using Graph Pooling for Graph Clustering [37.68977275752782]
  ノイズの多いエッジとグラフのノードは、クラスタリング結果を悪化させる可能性がある。 ノイズの多いノードやエッジに対するグラフクラスタリングの堅牢性を改善するために,新しいデュアルグラフ埋め込みネットワーク(DGEN)を提案する。 3つのベンチマークグラフデータセットの実験は、いくつかの最先端アルゴリズムと比較して優位性を示す。
  論文  参考訳（メタデータ） (2021-04-30T06:51:51Z)
• Graph Neural Networks with Adaptive Frequency Response Filter [55.626174910206046]
  適応周波数応答フィルタを用いたグラフニューラルネットワークフレームワークAdaGNNを開発した。 提案手法の有効性を,様々なベンチマークデータセット上で実証的に検証した。
  論文  参考訳（メタデータ） (2021-04-26T19:31:21Z)

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

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