On the average sensitivity of the weighted sum function

DOI10.1016/j.ipl.2011.11.001zbMath1253.68178OpenAlexW2031415846MaRDI QIDQ413263

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 complexityBoolean functionweightaverage sensitivitysubset sum

Mathematics Subject Classification ID

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

Related Items (3)

Boolean nested canalizing functions: a comprehensive analysis ⋮ A new sieve for restricted multiset counting ⋮ The simplified weighted sum function and its average sensitivity

Cites Work

• Unnamed Item
• The average sensitivity of bounded-depth circuits
• Lower bounds of quantum black-box complexity and degree of approximating polynomials by influence of Boolean variables
• A new sieve for distinct coordinate counting
• Counting subset sums of finite Abelian groups
• Sensitivity vs. block sensitivity (an average-case study)
• On the subset sum problem over finite fields
• A read-once lower bound and a \((1,+k)\)-hierarchy for branching programs
• The average sensitivity of square-freeness
• Quantum branching programs and space-bounded nonuniform quantum complexity
• Complexity measures and decision tree complexity: a survey.
• Sensitivity vs. block sensitivity of Boolean functions
• Laced Boolean functions and subset sum problems in finite fields
• Bounds on the Fourier coefficients of the weighted sum function
• The Difference Between Consecutive Primes, II

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