A NOTE ON A CONJECTURE CONCERNING SYMMETRICAL RESILIENT FUNCTIONS

被引：28

作者：

GOPALAKRISHNAN, K

HOFFMAN, DG

STINSON, DR

机构：

[1] UNIV NEBRASKA,DEPT COMP SCI & ENGN,FERGUSON HALL,POB 880115,LINCOLN,NE 68588

[2] UNIV NEBRASKA,CTR COMMUN & INFORMAT SCI,LINCOLN,NE 68588

[3] AUBURN UNIV,DEPT COMP SCI & ENGN,AUBURN,AL 36849

来源：

INFORMATION PROCESSING LETTERS | 1993年 / 47卷 / 03期

基金：

美国国家科学基金会;

关键词：

THEORY OF COMPUTATION; SYMMETRICAL RESILIENT FUNCTIONS; CRYPTOGRAPHY; SUBSET SUM;

D O I：

10.1016/0020-0190(93)90237-4

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

In 1985, Chor et al. conjectured that the only 1-resilient symmetric functions are the exclusive-or of all n variables and its negation. In this note the existence of symmetric resilient functions is shown to be equivalent to the existence of a solution to a simultaneous subset sum problem. Then, using arithmetic properties of certain binomial coefficients, an infinite class of counterexamples to the conjecture is obtained.

引用

页码：139 / 143

页数：5