On the average sensitivity of the weighted sum function

DOI10.1016/J.IPL.2011.11.001zbMATH Open1253.68178OpenAlexW2031415846MaRDI QIDQ413263FDOQ413263

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

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 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)

Cites Work

• The difference between consecutive primes. II
• A new sieve for distinct coordinate counting
• On the subset sum problem over finite fields
• The average sensitivity of bounded-depth circuits
• Sensitivity vs. block sensitivity of Boolean functions
• Lower bounds of quantum black-box complexity and degree of approximating polynomials by influence of Boolean variables
• Sensitivity vs. block sensitivity (an average-case study)
• Complexity measures and decision tree complexity: a survey.
• Counting subset sums of finite Abelian groups
• Bounds on the Fourier coefficients of the weighted sum function
• 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
• Laced Boolean functions and subset sum problems in finite fields
• Title not available (Why is that?)

Cited In (5)

• 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
• The simplified weighted sum function and its average sensitivity

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)