論文の概要: Round and Communication Balanced Protocols for Oblivious Evaluation of
Finite State Machines
- arxiv url: http://arxiv.org/abs/2103.11240v1
- Date: Sat, 20 Mar 2021 20:49:41 GMT
- ステータス: 処理完了
- システム内更新日: 2021-03-23 14:15:33.521134
- Title: Round and Communication Balanced Protocols for Oblivious Evaluation of
Finite State Machines
- Title(参考訳): 有限状態マシンの公開評価のためのラウンド・コミュニケーションバランスプロトコル
- Authors: Rafael Dowsley and Caleb Horst and Anderson C. A. Nascimento
- Abstract要約: 有限状態機械を不明瞭に評価するためのプロトコルを提案する。
評価は有限状態マシンのプロバイダと入力文字列のプロバイダとの間で共有される。
我々はこの問題に対する2つの異なる解決法、すなわち、信頼できないが解決しないヘルパーをセットとして提示する。
- 参考スコア(独自算出の注目度): 12.427126681901482
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We propose protocols for obliviously evaluating finite-state machines, i.e.,
the evaluation is shared between the provider of the finite-state machine and
the provider of the input string in such a manner that neither party learns the
other's input, and the states being visited are hidden from both. For alphabet
size $|\Sigma|$, number of states $|Q|$, and input length $n$, previous
solutions have either required a number of rounds linear in $n$ or
communication $\Omega(n|\Sigma||Q|\log|Q|)$. Our solutions require 2 rounds
with communication $O(n(|\Sigma|+|Q|\log|Q|))$. We present two different
solutions to this problem, a two-party one and a setting with an untrusted but
non-colluding helper.
- Abstract(参考訳): 本研究では,有限状態機械のプロバイダと入力文字列のプロバイダとの間で,双方が相手の入力を学習せず,訪れた状態が両方から隠蔽されるように,その評価を明示的に評価するためのプロトコルを提案する。
アルファベットサイズ $|\sigma|$, 状態数 $|q|$, 入力長 $n$ に対して、以前の解は数ラウンドを$n$ で直線化するか、$\omega(n|\sigma||q|\log|q|)$ で通信する必要があった。
我々の解は通信$O(n(|\Sigma|+|Q|\log|Q|))$の2ラウンドを必要とする。
我々はこの問題に対する2つの異なる解決法、すなわち、信頼できないが解決しないヘルパーをセットとして提示する。
関連論文リスト
- Nearly-Optimal Consensus Tolerating Adaptive Omissions: Why is a Lot of Randomness Needed? [4.465134753953128]
同期分散システムにおいて,通信リンクから障害当事者への通信がメッセージの送信を省略できる場合,$n$の自律的パーティによる合意に達するという問題について検討する。
我々は、$O(sqrtnlog2 n)$ラウンドで動作し、$O(n2log3 n)$通信ビットを送信するランダム化アルゴリズムを設計する。
MCアルゴリズムが$O(R)$呼び出しを使用する場合、$Omega(fracn2maxR,nlog n)$ラウンドで動作しないことを示す。
論文 参考訳(メタデータ) (2024-05-08T02:17:10Z) - Dimension Independent Disentanglers from Unentanglement and Applications [55.86191108738564]
両部非絡み込み入力から次元独立なk-パーティイトディジアンタングル(類似)チャネルを構築する。
NEXP を捉えるためには、$| psi rangle = sqrta | sqrt1-a | psi_+ rangle という形の非負の振幅を持つのに十分であることを示す。
論文 参考訳(メタデータ) (2024-02-23T12:22:03Z) - Unitarity estimation for quantum channels [7.323367190336826]
ユニタリティ推定は、量子デバイス認証とベンチマークにおいて基礎的で重要な問題である。
我々は、アンシラ効率のアルゴリズムを誘導するユニタリティ推定のための統一的なフレームワークを提供する。
アルゴリズムの$d$-dependenceと$epsilon$-dependenceの両方が最適であることを示す。
論文 参考訳(メタデータ) (2022-12-19T09:36:33Z) - A Framework for Distributed Quantum Queries in the CONGEST Model [0.0]
量子クエリアルゴリズムを量子CONGESTで実装するための一般的なフレームワークを提供する。
分散Deutsch-Jozsa問題に対するプロトコルを一般化する。
また、サイクル検出と計算の問題を量子スピードアップする。
論文 参考訳(メタデータ) (2022-02-22T15:18:39Z) - Testing matrix product states [5.225550006603552]
未知の状態$|psirangle$が特性試験モデルにおける行列積状態(MPS)かどうかをテストする。
MPS(英: MPS)は、量子多体系の研究で生じる物理関連量子状態のクラスである。
論文 参考訳(メタデータ) (2022-01-05T21:10:50Z) - Distributed Saddle-Point Problems Under Similarity [173.19083235638104]
与えられたサブ最適度$epsilon0$は、$Omegabigのマスター/ワーカーネットワークで達成されることを示す。
次に,ネットワークの下位の型(ログオーバまで)に適合するアルゴリズムを提案する。
頑健なロジスティック回帰問題に対して提案アルゴリズムの有効性を評価する。
論文 参考訳(メタデータ) (2021-07-22T14:25:16Z) - A Sample-Efficient Algorithm for Episodic Finite-Horizon MDP with
Constraints [8.849815837266977]
制約付きマルコフ決定プロセス(CMDP)は、シーケンシャルな意思決定問題を定式化する。
本稿では, 有限水平CMDPの線形計画法を利用して, 繰り返し楽観的な計画を立てるオンラインアルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-09-23T19:30:46Z) - On Distributed Differential Privacy and Counting Distinct Elements [52.701425652208734]
我々は、$n$ユーザのそれぞれが離散集合から要素を保持する設定について研究する。
目標は、すべてのユーザーに対して異なる要素の数を数えることだ。
論文 参考訳(メタデータ) (2020-09-21T04:13:34Z) - 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) - Quantum Differentially Private Sparse Regression Learning [132.1981461292324]
我々は、スパース回帰問題を解くために、効率的な量子微分プライベート(QDP)ラッソ推定器を考案する。
最後に、QDP Lasso はプライバシー保証付きで $tildeO(N-2/3)$ に近い最適ユーティリティを実現していることを示す。
論文 参考訳(メタデータ) (2020-07-23T10:50:42Z) - Tight Quantum Lower Bound for Approximate Counting with Quantum States [49.6558487240078]
Aaronson, Kothari, Kretschmer, Thaler (2020) が考える数え上げ問題の次の変種に対する厳密な下界を証明する。
このタスクは、入力セット$xsubseteq [n]$が$k$か$k'=(1+varepsilon)k$であるかどうかを識別する。
論文 参考訳(メタデータ) (2020-02-17T10:53:50Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。