On the average sensitivity of the weighted sum function

DOI10.1016/J.IPL.2011.11.001MaRDI QIDQ413263zbMATH OpenOpenAlexFDO

Authors Jiyou Li

Publication date 4 May 2012

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

Full work available at URL https://doi.org/10.1016/j.ipl.2011.11.001

zbMATH Keywords

computational complexityweightBoolean functionsubset sumaverage sensitivity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Other combinatorial number theory (11B75) Boolean functions (94D10)

Recommendations

• The simplified weighted sum function and its average sensitivity
• The average sensitivity of square-freeness
• Laced Boolean functions and subset sum problems in finite fields
• Tight bounds on the average sensitivity of k-CNF
• scientific article; zbMATH DE number 4218320

Cites work

• scientific article; zbMATH DE number 1962823 (Why is no real title available?)
• A new sieve for distinct coordinate counting
• A read-once lower bound and a \((1,+k)\)-hierarchy for branching programs
• Bounds on the Fourier coefficients of the weighted sum function
• Complexity measures and decision tree complexity: a survey.
• 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 subset sum problem over finite fields
• 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 difference between consecutive primes. II

Cited in

(6)

• The simplified weighted sum function and its average sensitivity
• Analyzing a weighted digital sum variant
• The average sensitivity of square-freeness
• A new sieve for restricted multiset counting
• On the average sensitivity of laced Boolean functions
• Boolean nested canalizing functions: a comprehensive analysis

This page was built for publication: On the average sensitivity of the weighted sum function

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