The simplified weighted sum function and its average sensitivity
From MaRDI portal
Publication:5964818
DOI10.1016/J.IPL.2016.01.002zbMath1352.68073arXiv1412.6268OpenAlexW1634111577MaRDI QIDQ5964818
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
Analysis of algorithms and problem complexity (68Q25) Boolean functions (06E30) Data structures (68P05)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A simple function that requires exponential size read-once branching programs
- The average sensitivity of bounded-depth circuits
- Lower bounds of quantum black-box complexity and degree of approximating polynomials by influence of Boolean variables
- On the average sensitivity of the weighted sum function
- A new sieve for distinct coordinate counting
- Counting subset sums of finite Abelian groups
- Sensitivity vs. block sensitivity (an average-case study)
- The critical number of finite abelian groups
- Entropy of contact circuits and lower bounds on their complexity
- 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
- A well-mixed function with circuit complexity \(5n\): tightness of the Lachish-Raz-type bounds
- On the Average Sensitivity and Density of k-CNF Formulas
- Cyclic Spaces for Grassmann Derivatives and Additive Theory
- Branching Programs and Binary Decision Diagrams
This page was built for publication: The simplified weighted sum function and its average sensitivity
