Lower Bounds on Balancing Sets and Depth-2 Threshold Circuits

DOI10.4230/LIPIcs.ICALP.2019.72OpenAlexW2966705569MaRDI QIDQ5091231

Ramamoorthy Sivaramakrishnan Natarajan, Amir Yehudayoff, Anup Rao, Pavel Hrubeš

Publication date: 21 July 2022

Full work available at URL: https://doi.org/10.4230/LIPIcs.ICALP.2019.72

zbMATH Keywords

polynomialsmajoritybalancing setsdepth-2 threshold circuitsweighted thresholds

Mathematics Subject Classification ID

Theory of computing (68Qxx) Theory of software (68Nxx)

Related Items (3)

\(d\)-Galvin families ⋮ On Expressing Majority as a Majority of Majorities ⋮ \(L\)-balancing families

Cites Work

• Unnamed Item
• Kneser's conjecture, chromatic number, and homotopy
• Sorting in \(c \log n\) parallel steps
• Codes with given distances
• From discrepancy to majority
• The Difference Between Consecutive Primes, II
• Short monotone formulae for the majority function
• A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits
• Amplifying lower bounds by means of self-reducibility
• Lower Bounds for Syntactically Multilinear Algebraic Branching Programs
• Forbidden Intersections
• Balancing sets of vectors
• Balancing sets of vectors

This page was built for publication: Lower Bounds on Balancing Sets and Depth-2 Threshold Circuits