了解使用随机算法的多项式平等测试 -- algorithms 领域 和 probability-theory 领域 和 randomized-algorithms 领域 和 probabilistic-algorithms 领域 cs 相关 的问题

Understanding polynomial equality testing using randomized algorithms


简体版||繁體版
-1
vote

问题

中文

文件从服务器下载,表示为$ a = {0,1 } ^ n $。服务器与$ b = {0,1 } ^ n $。我们希望使用随机算法确保$ a = b $确保一定程度的确定性。

以下是以下是从此引用的过程讲座pdf

输入图像描述

我无法围绕为什么有必要的一些步骤。所以这些是我的问题。

1)在步骤1中,我认为应该选择$ c cdot n $,因为如果$ m = 2 ^ {n-1} $,它会击败目的,我们最终以$ o(n)$,而不是$ o( log n)$;右?

2)在步骤2中,我们正在挑选素数。为什么需要素质?为什么我们不能只选择$ M $?

3)在步骤3& 4,我们选择一个随机值$ r $,并计算$ a(r)( mod p)$。为什么我们不能简单地计算$ a_ {dec} mod p $? $ a_ {dec} $是二进制字符串$ a $的十进制表示。然后,我们可以简单地比较$ a_ {dec} mod p $和$ b_ {dec} mod p $。

如果您可以展示其工作原理的示例,那将很受欢迎。假设我们有$ a = 101100 $和$ b = 111100 $,我们如何使用该算法比较它们?

谢谢。

英文原文

A file is downloaded from a server and is represented as $a = \{0, 1\}^n$. The server has that file as $b = \{0, 1\}^n$. We want to ensure a degree of certainty that $a=b$, using a randomized algorithm.

So below is the procedure referenced from this lecture pdf .

enter image description here

I can't get my head around why some of the steps are necessary. So these are my questions.

1) In step 1, I believe $M$ should be chosen as $c \cdot n$, since if $M = 2^{n-1}$, it would defeat the purpose and we end up with $O(n)$, instead of $O(\log n)$; right ?

2) In step 2, we are picking a prime. Why is a prime necessary ? why can't we simply choose $M$ ?

3) In steps 3 & 4, we pick a random value $r$ and compute $a(r)(\mod p)$. Why can't we simply compute $a_{dec} \mod p$ ? where $a_{dec}$ is the decimal representation of the binary string $a$. Then, we could simply compare $a_{dec} \mod p$ and $b_{dec} \mod p$.

If you could lay down an example of how this works, it would be much appreciated. Let's say we have $a = 101100$ and $b = 111100$, how do we go about comparing them using this algorithm ?

Thanks.

           
 
 

回答列表

1
 
vote

您的讲义说明包含您问题的答案。这里有一些提示。

1)在步骤1中,我相信$ C应该选择$ C CDOT N $,因为如果$ m = 2 ^ nÂ1$,它会击败目的,我们最终以$ o结束(n)$,而不是$ o( log n)$;右?

是。这正是我们选择通过有限字段(Modulo A Prime $ P $)而不是整数的原因。我们做所有计算$ bmod p $,保证我们永远不需要超过$ o( log p p)$ bits。

2)在步骤2中,我们正在挑选素数。为什么需要素质?为什么我们不能只选择$ M $?

我们决定使用一个有限的现场模数,是Prime $ P $。 $ p $在步骤4)和步骤5)。

3)在步骤3& 4,我们选择一个随机值$ r $,并计算$ a(r)( bmod p)$。为什么我们不能简单地计算$ a_ {dec} bmod p $?

我们正在考虑一个字符串作为多项式: $$ a(x)= sum_ {i = 1} ^ {n} a_i x ^ i $$ 并以$ r $评估它。 毕竟,我们正在做多项式标识测试。 但是,$ a_ {dec} $与$ r $和多项式(评估)无关。

 

Your lecture note contains the answer to your questions. Here are some hints.

1) In step 1, I believe $M$ should be chosen as $c \cdot n$, since if $M=2^n xe2x88x92 1$, it would defeat the purpose and we end up with $O(n)$, instead of $O(\log n)$; right?

Yes. That is exactly why we choose to work over a finite field (modulo a prime $p$) instead of over the whole integers. We do all calculations $\bmod p$, which guarantees that we never need more than $O(\log p)$ bits.

2) In step 2, we are picking a prime. Why is a prime necessary ? why can't we simply choose $M$?

We have decided to work over a finite field modulo a prime $p$. $p$ is used in step 4) and step 5).

3) In steps 3 & 4, we pick a random value $r$ and compute $a(r)(\bmod p)$. Why can't we simply compute $a_{dec} \bmod p$?

We are thinking of a string as a polynomial: $$a(x) = \sum_{i=1}^{n} a_i x^i$$ and evaluate it at $r$. After all, we are doing Polynomial Identity Testing. However, $a_{dec}$ has nothing to do with $r$ and polynomial (evaluation).

 
 

相关问题

3  证明$ IP ^ star = np $  ( Proving ip star np ) 
考虑以下复杂性类$ ip ^ star $,$ ip $的变体。 一种语言$ l $的$ ip ^ star $如果有校样系统$(p,v)$ s.t. $ V $是多项式时间和:的验证者 $$ x in l 意味着pr [(p,v)(x)= 1] ge 3/4 \ x not in l 意味着...

2  是否有一些分布的数学特性,其是概率多项式图定型机的输出?  ( Is there some mathematical properties of the distribution which is the output of ) 
让$ s_ {n} $是一个输入集,其元素为长度$ n $,即$ s_ {n} = sigma ^ {n} $。对于每个概率多项式算法$ a $和任何$ u in sigma ^ {*} $,存在一个函数$ f ^ {a} $,使得$ f ^ a(u)= mathrm {pr} [a(u)= 1] $。让$ ...

6  BPP搜索:提升正确性是什么?  ( Bpp search what does boosting correctness entail ) 
对我来说并不是很清楚,如何以及如果我可以在 bpp (有界误差概率多项式 - 时间)搜索问题。你们中的任何人都可以解释我如何工作? 使用BPP搜索,我的意思是一个可能具有假正负,正确解决方案和无解决方案的问题。这是一个定义: 概率的多项式算法$ a $解决关系的搜索问题$ r $如果 每一次$ x∈s $,$ pr...

0  PCP定理的参考  ( Reference on pcp theorem ) 
有人可以推荐关于PCP定理的引用,该PCP定理解释了如何通过示例而不是正式的CS语言工作? 具体来说,我正在寻找如何修改图形着色的示例,以便检查几个彩色或类似的东西。 在CSTHEORY.STACKEXCHANGE被要求将其移到此处。 ...

1  PCP定理中的多项式是什么?  ( Whats the polynomial involved in the pcp theorem ) 
pcp定理始终谈论长度$ poly(n)的证明$。但是那种多项式是什么?你能在现实生活中实际构建PCP吗? ...

3  绽放过滤器为20800万URL  ( Bloom filter for 208 million urls ) 
我需要创建一个208万URL的绽放过滤器。什么是偏航尺寸和哈希数量的良好选择?我尝试了大小的1 GB和4个哈希函数的位矢量,但它导致读取时的误报了太多。 我有一个包含数十亿个URL的Web内容的巨大Web语料库。我需要处理满足某些标准的URL的Web内容:URL应该在过去7天内在Web搜索结果中出现,至少5次。这由2...

0  散列算法最小化分布  ( Hashing algorithm which minimizes distribution ) 
考虑应用 A1, A2 .. AN 具有属性 P11, P12,... PN1, PN2..我们有以下约束 - total number of properties >> number of applications total number of properties >> number of bucke...

4  理论上了解模拟退火信息  ( Understanding simulated annealing information theoretically ) 
所以我最近重新发现了模拟退火,但其他人似乎很清楚的道路。我知道Metropolis-Hastings作为一种采样算法,它创造了一个Markov-Chain,该链条是通过归一化一些功能而产生的分布。意识到您可以使用它来优化许多事物,并且您甚至可以继续拒绝,这是一个很小的飞跃,甚至可以抵制到目前为止你发现的最少值。但是更...

1  统一采样与约束  ( Uniform sampling with constraints ) 
假设一个人想要在有限的字母表上统一地样本一个给定长度的字符串,这是$ w $满足一组结构约束(例如 - "第三个字符必须等于第一个字符和最后一个字符必须等于第二个")。 显而易见的方法是统一样本$ W $,检查约束是否保持并返回它。但是,我正在处理有许多限制的情况,随机字符串满足它们的概率非常低。有没有办法从满足一组...

0  如何在设定值随机变量上实施条件概率分布  ( How to implement conditional probability distribution on set valued random varia ) 
当两个RV的事件被设置时,我正在尝试实施条件概率分布。如果我尝试从真实或分类变量推断概念,以便为我设置令人困惑。在通常的场景中,对于某些分立的RVS, $ X,Y $ ,我们可以使用贝叶斯定理来计算两个"准时" 事件的条件概率: $$ p(y = y | x = x)= frac {p(x = x | y = y...




© 2022 it.wenda123.org All Rights Reserved. 问答之家 版权所有