8 citations · 11 across the 3 of their papers we have counts for
3 papers
math.CO2021★ 2 cited
The Gotsman-Linial Conjecture is False
Brynmor Chapman
In 1991, Craig Gotsman and Nathan Linial conjectured that for all and , the average sensitivity of a degree- polynomial threshold function on variables is maximized b…
cs.CC2021★ 1 cited
Smaller ACC0 Circuits for Symmetric Functions
Brynmor Chapman, Ryan Williams
What is the power of constant-depth circuits with gates, that can count modulo ? Can they efficiently compute MAJORITY and other symmetric functions? When is a const…
cs.CC2018★ 8 cited
Effective Divergence Analysis for Linear Recurrence Sequences
Shaull Almagor, Brynmor Chapman, Mehran Hosseini +2
We study the growth behaviour of rational linear recurrence sequences. We show that for low-order sequences, divergence is decidable in polynomial time. We also exhibit a polynomia…