{'fraction_non_alphanumeric': 0.04205128205128205, 'fraction_numerical': 0.011282051282051283, 'mean_word_length': 4.809523809523809, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
The Power of Asymmetry in Constant-Depth Circuits

The threshold degree of a Boolean function f is the minimum degree of a real polynomial p that represents f in sign: f(x) = sgn p(x). Introduced in the seminal work of Minsky and Papert (1969), this notion is central to some of the strongest algorithmic and complexity-theoretic results for constant-depth circuits. One problem that has remained open for several decades, with applications to computational learning and communication complexity, is to determine the maximum threshold degree of a polynomial-size constant-depth circuit in n variables. The best lower bound prior to our work was Ω(n(d-1)/(2d-1)) for circuits of depth d. We obtain a polynomial improvement for every depth d, with a lower bound of Ω(n3/7) for depth 3 and Ω(√n) for depth d ≥4. The proof contributes a novel approximation-theoretic technique of independent interest, which exploits asymmetry in circuits to prove their hardness for polynomials.