【24h】

Tight Lower Bounds for Testing Linear Isomorphism

机译:测试线性同构的紧下界

获取原文
获取原文并翻译 | 示例

摘要

We study lower bounds for testing membership in families of linear/affine-invariant Boolean functions over the hypercube. Motivated by the recent resurgence of attention to the permutation isomorphism problem, we first focus on families that are linearly/afEnely isomorphic to some fixed function. Our main result is a tight adaptive, two-sided Ω{n2) lower bound for testing linear isomorphism to the inner-product function. This is the first lower bound for testing linear isomorphism to a specific function that matches the trivial upper bound. Our proof exploits the elegant connection between testing and communication complexity discovered by Blais et al. (Computational Complexity, 2012.) Our second result shows an Ω(2~(n/4)) query lower bound for any adaptive, two-sided tester for membership in the Maiorana-McFarland class of bent functions. This class of Boolean functions is also affine-invariant and its rich structure and pseudorandom properties have been well-studied in mathematics, coding theory and cryptography.
机译:我们研究了在超立方体上测试线性/仿射不变布尔函数族中隶属关系的下限。出于对排列同构问题最近的关注的重新兴起,我们首先关注那些对某些固定函数呈线性/适当同构的族。我们的主要结果是紧密的自适应两侧Ω{n2)下界,用于测试内积函数的线性同构。这是将线性同构测试为与平凡的上限匹配的特定函数的第一个下限。我们的证明利用了Blais等人发现的测试与通信复杂性之间的精妙联系。 (计算复杂度,2012年。)我们的第二个结果表明,对于适应弯折函数的Maiorana-McFarland类的任何自适应双面测试器,Ω(2〜(n / 4))查询下界。这类布尔函数也是仿射不变的,并且其丰富的结构和伪随机性质已在数学,编码理论和密码学中得到了很好的研究。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号