Lower Bounds on Balancing Sets and Depth-2 Threshold Circuits

No abstract is available for this paper.

• Publication year

  2019

• Venue

  Electron. Colloquium Comput. Complex.

• Publication date

  Unknown publication date

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.4230/LIPIcs.ICALP.2019.72
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• On Expressing Majority as a Majority of Majorities

  2020cited by this paper
• d-Galvin Families

  2019cited by this paper
• Depth Two Majority Circuits for Majority and List Expanders

  2018cited by this paper
• Limits on representing Boolean functions by linear combinations of simple functions: thresholds, ReLUs, and low-degree polynomials

  2018influential reference
• Depth Two (n-2)-Majority Circuits for n-Majority

  2018cited by this paper
• Computing majority with low-fan-in majority queries

  2017influential reference
• Unbalancing Sets and An Almost Quadratic Lower Bound for Syntactically Multilinear Arithmetic Circuits

  2017cited by this paper
• Computing Majority by Constant Depth Majority Circuits with Low Fan-in Gates

  2016influential reference
• From Discrepancy to Majority

  2015cited by this paper
• Exact Threshold Circuits

  2010influential reference
• A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits

  2008cited by this paper
• Amplifying Lower Bounds by Means of Self-Reducibility

  2008cited by this paper
• Lower Bounds for Syntactically Multilinear Algebraic Branching Programs

  2008influential reference
• The Difference Between Consecutive Primes, II

  2001influential reference
• Balancing sets of vectors

  1988influential reference
• Codes with given distances

  1987influential reference
• Short Monotone Formulae for the Majority Function

  1984influential reference
• Sorting inc logn parallel steps

  1983cited by this paper
• Kneser's Conjecture, Chromatic Number, and Homotopy

  1978cited by this paper

• A Near-Optimal Polynomial Distance Lemma over Boolean Slices

  2025cites this paper
• Towards Simpler Sorting Networks and Monotone Circuits for Majority

  2023cites this paper
• The composition complexity of majority

  2022cites this paper
• Constant-Depth Sorting Networks

  2022cites this paper
• L-balancing families

  2022cites this paper
• $L$-balancing families

  2021cites this paper
• On Vanishing Properties of Polynomials on Symmetric Sets of the Boolean Cube, in Positive Characteristic

  2021cites this paper
• A robust version of Hegedus’s lemma, with applications

  2020influential citation
• d-Galvin Families

  2019cites this paper
• More on AC0[⊕] and Variants of the Majority Function

  2019cites this paper