The simplified weighted sum function and its average sensitivity

DOI10.1016/J.IPL.2016.01.002MaRDI QIDQ5964818zbMATH OpenOpenAlexFDO

Authors Jiyou Li, Chu Luo

Publication date 1 March 2016

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1412.6268

zbMATH Keywords

average sensitivityBoolean functioncomputational complexitysubset countingweighted sum function

Mathematics Subject Classification ID

Boolean functions (06E30) Data structures (68P05) Analysis of algorithms and problem complexity (68Q25)

Abstract: In this paper we simplify the definition of the weighted sum Boolean function which used to be inconvenient to compute and use. We show that the new function has essentially the same properties as the previous one. In particular, the bound on the average sensitivity of the weighted sum Boolean function remains unchanged after the simplification.

Recommendations

• On the average sensitivity of the weighted sum function
• Boolean functions with low average sensitivity depend on few coordinates
• On the sensitivity to noise of a Boolean function
• Laced Boolean functions and subset sum problems in finite fields
• Tight bounds on the average sensitivity of k-CNF

Cites work

• A new sieve for distinct coordinate counting
• A read-once lower bound and a \((1,+k)\)-hierarchy for branching programs
• A simple function that requires exponential size read-once branching programs
• A well-mixed function with circuit complexity \(5n\): tightness of the Lachish-Raz-type bounds
• Bounds on the Fourier coefficients of the weighted sum function
• Branching Programs and Binary Decision Diagrams
• Complexity measures and decision tree complexity: a survey.
• Cyclic Spaces for Grassmann Derivatives and Additive Theory
• Entropy of contact circuits and lower bounds on their complexity
• scientific article; zbMATH DE number 549860 (Why is no real title available?)
• scientific article; zbMATH DE number 1962823 (Why is no real title available?)
• scientific article; zbMATH DE number 1405644 (Why is no real title available?)
• Laced Boolean functions and subset sum problems in finite fields
• Lower bounds of quantum black-box complexity and degree of approximating polynomials by influence of Boolean variables
• On the average sensitivity and density of k-CNF formulas
• On the average sensitivity of the weighted sum function
• Quantum branching programs and space-bounded nonuniform quantum complexity
• Sensitivity vs. block sensitivity (an average-case study)
• Sensitivity vs. block sensitivity of Boolean functions
• The average sensitivity of bounded-depth circuits
• The average sensitivity of square-freeness
• The critical number of finite abelian groups
• Tight bounds on the average sensitivity of k-CNF

Cited in

(2)

• On the average sensitivity of the weighted sum function
• Robust topology optimization for periodic structures by combining sensitivity averaging with a semianalytical method

This page was built for publication: The simplified weighted sum function and its average sensitivity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5964818)