咨询与建议

限定检索结果

文献类型

  • 7 篇 期刊文献
  • 3 篇 会议

馆藏范围

  • 10 篇 电子文献
  • 0 种 纸本馆藏

日期分布

学科分类号

  • 8 篇 工学
    • 8 篇 计算机科学与技术...
    • 3 篇 电气工程
  • 6 篇 理学
    • 6 篇 数学
  • 1 篇 管理学
    • 1 篇 管理科学与工程(可...

主题

  • 10 篇 boolean function...
  • 3 篇 circuit complexi...
  • 2 篇 computational co...
  • 1 篇 lower bounds on ...
  • 1 篇 circuit simulati...
  • 1 篇 symmetric functi...
  • 1 篇 polynomial inter...
  • 1 篇 modular counting
  • 1 篇 sensitivity
  • 1 篇 reconfigurable c...
  • 1 篇 computer-aided d...
  • 1 篇 parity
  • 1 篇 multivariate pol...
  • 1 篇 decision tree
  • 1 篇 symmetrical bool...
  • 1 篇 p equals np
  • 1 篇 lower bound
  • 1 篇 degree lower bou...
  • 1 篇 mobius inversion
  • 1 篇 approximate majo...

机构

  • 1 篇 naval postgrad s...
  • 1 篇 multimedia univ ...
  • 1 篇 natl chiao tung ...
  • 1 篇 indian inst tech...
  • 1 篇 dept. of comput....
  • 1 篇 department of co...
  • 1 篇 natl chi nan uni...
  • 1 篇 cwi nl-1009 ab a...
  • 1 篇 univ massachuset...
  • 1 篇 stanford univ st...
  • 1 篇 meiji univ dept ...
  • 1 篇 united arab emir...
  • 1 篇 hungarian acad s...
  • 1 篇 mit 77 massachus...
  • 1 篇 stanford univ st...

作者

  • 1 篇 barrington dam
  • 1 篇 butler jon t.
  • 1 篇 yang mng-chuan
  • 1 篇 tsai sc
  • 1 篇 tsai shi-chun
  • 1 篇 blanc guy
  • 1 篇 sasao tsutomu
  • 1 篇 lange jane
  • 1 篇 de graaf m
  • 1 篇 tardos g
  • 1 篇 valiant p
  • 1 篇 beg azam
  • 1 篇 nwana gf
  • 1 篇 tan li-yang
  • 1 篇 prasad p. w. cha...
  • 1 篇 tsai stc
  • 1 篇 leng ph
  • 1 篇 koch caleb
  • 1 篇 dunne pe
  • 1 篇 sanyal swagato

语言

  • 10 篇 英文
检索条件"主题词=Boolean function complexity"
10 条 记 录,以下是1-10 订阅
Randomized Query Composition and Product Distributions  41
Randomized Query Composition and Product Distributions
收藏 引用
41st International Symposium on Theoretical Aspects of Computer Science (STACS)
作者: Sanyal, Swagato Indian Inst Technol Kharagpur Dept Comp Sci & Engn Kharagpur India
Let RE denote randomized query complexity for error probability epsilon, and R := R-1/3. In this work we investigate whether a perfect composition theorem R(f o g(n)) = Omega(R(f) center dot R(g)) holds for a relation... 详细信息
来源: 评论
The Query complexity of Certification  2022
The Query Complexity of Certification
收藏 引用
54th Annual ACM SIGACT Symposium on Theory of Computing (STOC)
作者: Blanc, Guy Koch, Caleb Lange, Jane Tan, Li-Yang Stanford Univ Stanford CA 94305 USA MIT 77 Massachusetts Ave Cambridge MA 02139 USA
We study the problem of certification: given queries to a function f : {0, 1}(n) ->{0, 1} with certificate complexity <= k and an input x(star), output a size-k certificate for f's value on x(star). For mono... 详细信息
来源: 评论
On the Sensitivity of boolean and Multiple-Valued Symmetric functions  52
On the Sensitivity of Boolean and Multiple-Valued Symmetric ...
收藏 引用
52nd IEEE International Symposium on Multiple-Valued Logic (ISMVL)
作者: Butler, Jon T. Sasao, Tsutomu Naval Postgrad Sch Dept Elect & Comp Engn Monterey CA 93943 USA Meiji Univ Dept Comp Sci & Elect Kawasaki Kanagawa 2148571 Japan
An n-variable boolean logic function f((x) over right arrow) is sensitive to x(i) if there is at least one assignment of values to (x) over right arrow - {x(i)} such that f changes when x(i) changes. We investigate th... 详细信息
来源: 评论
Representing Symmetric boolean functions with Polynomial over Composite Moduli
收藏 引用
JOURNAL OF INFORMATION SCIENCE AND ENGINEERING 2018年 第1期34卷 193-203页
作者: Tsai, Shi-Chun Yang, Mng-Chuan Natl Chiao Tung Univ Dept Comp Sci Hsinchu 300 Taiwan
Polynomial degree is an important measure for studying the computational complexity of boolean function. A polynomial P is an element of Z(m)[x] is a generalized representation off over Z(m) if for all x, y is an elem... 详细信息
来源: 评论
Investigating data preprocessing methods for circuit complexity models
收藏 引用
EXPERT SYSTEMS WITH APPLICATIONS 2009年 第1期36卷 519-526页
作者: Prasad, P. W. Chandana Beg, Azam United Arab Emirates Univ Coll Informat Technol Al Ain U Arab Emirates Multimedia Univ Fac Informat Syst & Technol Cyberjaya Selangor Malaysia
Preprocessing the data is an important step while creating neural network (NN) applications because this step usually has a significant effect on the prediction performance of the model. This paper compares different ... 详细信息
来源: 评论
Polynomial representations of symmetric partial boolean functions
收藏 引用
SIAM JOURNAL ON DISCRETE MATHEMATICS 2005年 第2期19卷 481-488页
作者: De Graaf, M Valiant, P CWI NL-1009 AB Amsterdam Netherlands Stanford Univ Stanford CA 94309 USA
For boolean polynomials in Z(p) of sufficiently low degree we derive a relation expressing their values on one level set in terms of their values on another level set. We use this relation to derive linear upper and l... 详细信息
来源: 评论
A depth 3 circuit lower bound for the parity function
收藏 引用
JOURNAL OF INFORMATION SCIENCE AND ENGINEERING 2001年 第5期17卷 857-860页
作者: Tsai, STC Natl Chi Nan Univ Informat Management Dept Nantou 545 Taiwan
We consider small depth boolean circuits with basis {AND, OR, NOT}. We obtain lower bounds for the parity function using a relatively simple method. We prove that for any depth 3 circuit with top fan-in t, computing t... 详细信息
来源: 评论
A lower bound on the MOD 6 degree of the or function
收藏 引用
COMPUTATIONAL complexity 1998年 第2期7卷 99-108页
作者: Tardos, G Barrington, DAM Hungarian Acad Sci Inst Math H-1088 Budapest Hungary Univ Massachusetts Dept Comp Sci Amherst MA 01003 USA
We examine the computational power of modular counting, where the modulus m is not a prime power, in the setting of polynomials in boolean variables over Z(m). In particular, we say that a polynomial P weakly represen... 详细信息
来源: 评论
Lower bounds on representing boolean functions as polynomials in Z(m)
收藏 引用
SIAM JOURNAL ON DISCRETE MATHEMATICS 1996年 第1期9卷 55-62页
作者: Tsai, SC Department of Computer Science University of Chicago Chicago IL 60637 1100 East 58th Street United States
Define the MOD(m)-degree of a boolean function F to be the smallest degree of any polynomial P, over the ring of integers module m, such that for all 0-1 assignments ((x) over right arrow, F((x) over right arrow) = 0 ... 详细信息
来源: 评论
ON THE complexity OF boolean functionS COMPUTED BY LAZY ORACLES
收藏 引用
IEEE TRANSACTIONS ON COMPUTERS 1995年 第4期44卷 495-502页
作者: DUNNE, PE LENG, PH NWANA, GF Dept. of Comput. Sci. Liverpool Univ. UK
In this paper we introduce and examine some properties of a new complexity measure for boolean functions. Unlike classical approaches, which are largely concerned with resource requirements (see, e.g., [3]), the measu... 详细信息
来源: 评论