On the public citation graph
The expressive power of voting polynomials
0 signed · 162 inferred · view as graph
Inferred edges come from two machine sources: sweeps of open repository metadata (mostly SSRN and Zenodo), and a bulk OpenAlex citation snapshot. Every row below is labelled with the one it came from. Neither is a complete citation index — absence here is not evidence of absence.
Is this your work? Sign in with ORCID and put your name on the
claims that are yours.
Reference health. See whether every reference in this work resolves to a
known work and none has been retracted — and get a dated CiteStamped
badge you can embed.
What this work says
Outgoing claims: the papers this work cites, builds on, or argues with.
inferredcites →https://doi.org/10.1007/bf01137685openalex-snapshot
Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
inferredcites →https://doi.org/10.1007/bf01458147openalex-snapshot
�ber positive L�sungen homogener linearer Gleichungen
inferredcites →https://doi.org/10.1007/bf01744431openalex-snapshot
Parity, circuits, and the polynomial-time hierarchy
inferredcites →https://doi.org/10.1007/bfb0020802openalex-snapshot
Randomized polynomials, threshold circuits, and the polynomial hierarchy
inferredcites →https://doi.org/10.1016/0022-0000(91)90040-copenalex-snapshot
Relativized counting classes: Relations among thresholds, parity, and mods
inferredcites →https://doi.org/10.1016/b978-1-55860-146-8.50036-9openalex-snapshot
ON THRESHOLD CIRCUITS FOR PARITY
inferredcites →https://doi.org/10.1109/fscs.1990.89559openalex-snapshot
On threshold circuits for parity
inferredcites →https://doi.org/10.1109/fscs.1990.89585openalex-snapshot
Polynomial threshold functions, AC functions and spectrum norms
inferredcites →https://doi.org/10.1109/sfcs.1985.49openalex-snapshot
Separating the polynomial-time hierarchy by oracles
inferredcites →https://doi.org/10.1109/sfcs.1989.63537openalex-snapshot
Constant depth circuits, Fourier transform, and learnability
inferredcites →https://doi.org/10.1137/0210008openalex-snapshot
Relative to a Random Oracle A , ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
inferredcites →https://doi.org/10.1137/0221003openalex-snapshot
Polynomial Threshold Functions, $AC^0 $ Functions, and Spectral Norms
inferredcites →https://doi.org/10.1137/0403015openalex-snapshot
Harmonic Analysis of Polynomial Threshold Functions
inferredcites →https://doi.org/10.1145/174130.174138openalex-snapshot
Constant depth circuits, Fourier transform, and learnability
inferredcites →https://doi.org/10.1145/22145.22196openalex-snapshot
NP is as easy as detecting unique solutions
inferredcites →https://doi.org/10.1145/28395.28404openalex-snapshot
Algebraic methods in the theory of lower bounds for Boolean circuit complexity
inferredcites →https://doi.org/10.2307/253980openalex-snapshot
Theory of Linear and Integer Programming
What points at this work
Incoming claims: where this work appears in other papers’ reference lists and arguments.
inferred← citeshttps://doi.org/10.1006/inco.1994.1059openalex-snapshot
Approximating Threshold Circuits by Rational Functions
inferred← citeshttps://doi.org/10.1007/11523468_80openalex-snapshot
Lower Bounds for Circuits with Few Modular and Symmetric Gates
inferred← citeshttps://doi.org/10.1007/11750321_42openalex-snapshot
On PAC Learning Algorithms for Rich Boolean Function Classes
inferred← citeshttps://doi.org/10.1007/3-540-44666-4_28openalex-snapshot
On the Derandomization of Constant Depth Circuits
inferred← citeshttps://doi.org/10.1007/3-540-45687-2_18openalex-snapshot
Autoreducibility of Random Sets: A Sharp Bound on the Density of Guessed Bits
inferred← citeshttps://doi.org/10.1007/3-540-62034-6_33openalex-snapshot
Circuit complexity before the dawn of the new millennium
inferred← citeshttps://doi.org/10.1007/978-1-4612-1872-2_11openalex-snapshot
Polynomials and Combinatorial Definitions of Languages
inferred← citeshttps://doi.org/10.1007/978-1-4615-2696-4_1openalex-snapshot
Neural Models and Spectral Methods
inferred← citeshttps://doi.org/10.1007/978-3-319-55911-7_14openalex-snapshot
Learning $$AC^0$$ Under k-Dependent Distributions
inferred← citeshttps://doi.org/10.1007/978-3-319-62389-4_32openalex-snapshot
On the Modulo Degree Complexity of Boolean Functions
inferred← citeshttps://doi.org/10.1007/978-3-540-28629-5_24openalex-snapshot
Some Meet-in-the-Middle Circuit Lower Bounds
inferred← citeshttps://doi.org/10.1007/978-3-540-73545-8_44openalex-snapshot
Computing Symmetric Boolean Functions by Circuits with Few Exact Threshold Gates
inferred← citeshttps://doi.org/10.1007/978-3-540-92182-0_80openalex-snapshot
Unbounded-Error Quantum Query Complexity
inferred← citeshttps://doi.org/10.1007/978-3-642-15369-3_44openalex-snapshot
Learning and Lower Bounds for AC 0 with Threshold Gates
inferred← citeshttps://doi.org/10.1007/978-3-642-21111-9_32openalex-snapshot
Representing Boolean Functions Using Polynomials: More Can Offer Less
inferred← citeshttps://doi.org/10.1007/978-3-642-22685-4_53openalex-snapshot
A New Variation of Hat Guessing Games
inferred← citeshttps://doi.org/10.1007/978-3-642-22935-0_54openalex-snapshot
Correlation Bounds for Poly-size $\mbox{\rm AC}^0$ Circuits with n 1 − o(1) Symmetric Gates
inferred← citeshttps://doi.org/10.1007/978-3-642-60322-8_13openalex-snapshot
The Parity Function Again
inferred← citeshttps://doi.org/10.1007/pl00001599openalex-snapshot
A complex-number Fourier technique for lower bounds on the Mod-m degree
inferred← citeshttps://doi.org/10.1007/s00037-005-0203-0openalex-snapshot
On the computational power of Boolean decision lists
inferred← citeshttps://doi.org/10.1007/s00037-008-0244-2openalex-snapshot
Polynomials that Sign Represent Parity and Descartes’ Rule of Signs
inferred← citeshttps://doi.org/10.1007/s00037-009-0274-4openalex-snapshot
Approximate Inclusion-Exclusion for Arbitrary Symmetric Functions
inferred← citeshttps://doi.org/10.1007/s00037-010-0290-4openalex-snapshot
The Complexity of Boolean Functions in Different Characteristics
inferred← citeshttps://doi.org/10.1007/s00037-026-00296-9openalex-snapshot
A Technique for Hardness Amplification Against $$\textsf{AC}^0$$
inferred← citeshttps://doi.org/10.1007/s00493-010-2173-3openalex-snapshot
New degree bounds for polynomial threshold functions
inferred← citeshttps://doi.org/10.1007/s00493-011-2580-0openalex-snapshot
The Unbounded-Error Communication Complexity of Symmetric Functions
inferred← citeshttps://doi.org/10.1007/s00493-013-2759-7openalex-snapshot
Optimal bounds for sign-representing the intersection of two halfspaces by polynomials
inferred← citeshttps://doi.org/10.1007/s00493-014-3078-3openalex-snapshot
The communication complexity of addition
inferred← citeshttps://doi.org/10.1007/s10994-007-5010-1openalex-snapshot
Unconditional lower bounds for learning intersections of halfspaces
inferred← citeshttps://doi.org/10.1016/j.disc.2007.08.090openalex-snapshot
Problems and results in extremal combinatorics—II
inferred← citeshttps://doi.org/10.1016/j.ipl.2011.12.011openalex-snapshot
Exponential lower bound for bounded depth circuits with few threshold gates
inferred← citeshttps://doi.org/10.1016/j.jcss.2003.07.007openalex-snapshot
Learning DNF in time 2Õ(n1/3)
inferred← citeshttps://doi.org/10.1016/j.jcss.2003.11.002openalex-snapshot
Learning intersections and thresholds of halfspaces
inferred← citeshttps://doi.org/10.1016/j.jcss.2006.01.002openalex-snapshot
LWPP and WPP are not uniformly gap-definable
inferred← citeshttps://doi.org/10.1016/j.jcss.2007.06.021openalex-snapshot
Extremal properties of polynomial threshold functions
inferred← citeshttps://doi.org/10.1016/j.jcss.2019.04.004openalex-snapshot
Bounded depth circuits with weighted symmetric gates: Satisfiability, lower bounds and compression
inferred← citeshttps://doi.org/10.1016/j.neunet.2009.03.016openalex-snapshot
Sign-representation of Boolean functions using a small number of monomials
inferred← citeshttps://doi.org/10.1016/j.tcs.2011.04.043openalex-snapshot
Unbounded-error quantum query complexity
inferred← citeshttps://doi.org/10.1016/j.tcs.2018.04.049openalex-snapshot
On the modulo degree complexity of Boolean functions
inferred← citeshttps://doi.org/10.1016/s0012-365x(03)00227-9openalex-snapshot
Problems and results in extremal combinatorics—I
inferred← citeshttps://doi.org/10.1103/physreva.96.032321openalex-snapshot
Nonunitary quantum computation in the ground space of local Hamiltonians
inferred← citeshttps://doi.org/10.1109/18.312168openalex-snapshot
Rational approximation techniques for analysis of neural networks
inferred← citeshttps://doi.org/10.1109/ccc.2003.1214406openalex-snapshot
Extremal properties of polynomial threshold functions
inferred← citeshttps://doi.org/10.1109/ccc.2004.1313846openalex-snapshot
Polynomials that sign represent parity and descartes rule of signs
inferred← citeshttps://doi.org/10.1109/ccc.2004.25openalex-snapshot
Polynomials that sign represent parity and Descartes rule of signs
inferred← citeshttps://doi.org/10.1109/ccc.2006.32openalex-snapshot
Oracles Are Subtle But Not Malicious
inferred← citeshttps://doi.org/10.1109/ccc.2007.18openalex-snapshot
On Computation and Communication with Small Bias
inferred← citeshttps://doi.org/10.1109/ccc.2009.14openalex-snapshot
On the Complexity of Boolean Functions in Different Characteristics
inferred← citeshttps://doi.org/10.1109/ccc.2010.28openalex-snapshot
A Regularity Lemma, and Low-Weight Approximators, for Low-Degree Polynomial Threshold Functions
inferred← citeshttps://doi.org/10.1109/focs.2007.24openalex-snapshot
Computing Equilibria in Anonymous Games
inferred← citeshttps://doi.org/10.1109/focs.2007.28openalex-snapshot
Polylogarithmic Independence Can Fool DNF Formulas
inferred← citeshttps://doi.org/10.1109/focs.2007.30openalex-snapshot
Discrepancy and the Power of Bottom Fan-in in Depth-three Circuits
inferred← citeshttps://doi.org/10.1109/focs.2007.55openalex-snapshot
Smooth Histograms for Sliding Windows
inferred← citeshttps://doi.org/10.1109/focs.2009.18openalex-snapshot
The Intersection of Two Halfspaces Has High Threshold Degree
inferred← citeshttps://doi.org/10.1109/focs.2010.8openalex-snapshot
Bounded Independence Fools Degree-2 Threshold Functions
inferred← citeshttps://doi.org/10.1109/focs.2015.34openalex-snapshot
The Power of Asymmetry in Constant-Depth Circuits
inferred← citeshttps://doi.org/10.1109/focs.2016.57openalex-snapshot
Polynomial Representations of Threshold Functions and Algorithmic Applications
inferred← citeshttps://doi.org/10.1109/focs.2018.00094openalex-snapshot
Indistinguishability by Adaptive Procedures with Advice, and Lower Bounds on Hardness Amplification Proofs
inferred← citeshttps://doi.org/10.1109/istcs.1997.595166openalex-snapshot
Closure properties of GapP and #P
inferred← citeshttps://doi.org/10.1109/jsait.2021.3055341openalex-snapshot
Coded Computing for Secure Boolean Computations
inferred← citeshttps://doi.org/10.1109/sct.1993.336538openalex-snapshot
The polynomial method in circuit complexity
inferred← citeshttps://doi.org/10.1109/sfcs.1993.366874openalex-snapshot
On representations by low-degree polynomials
inferred← citeshttps://doi.org/10.1109/sfcs.2001.959893openalex-snapshot
Lower bounds for polynomial calculus: non-binomial case
inferred← citeshttps://doi.org/10.1109/sfcs.2002.1181894openalex-snapshot
Learning intersections and thresholds of halfspaces
inferred← citeshttps://doi.org/10.1134/s0001434610050263openalex-snapshot
A small decrease in the degree of a polynomial with a given sign function can exponentially increase its weight and length
inferred← citeshttps://doi.org/10.1137/070691954openalex-snapshot
Polylogarithmic Independence Can Fool DNF Formulas
inferred← citeshttps://doi.org/10.1137/08071421xopenalex-snapshot
Separating ${AC}^0$ from Depth-2 Majority Circuits
inferred← citeshttps://doi.org/10.1137/080735096openalex-snapshot
Hardness Amplification Proofs Require Majority
inferred← citeshttps://doi.org/10.1137/1.9781611973105.46openalex-snapshot
The communication complexity of addition
inferred← citeshttps://doi.org/10.1137/1.9781611974331.ch87openalex-snapshot
Deterministic APSP, Orthogonal Vectors, and More: Quickly Derandomizing Razborov-Smolensky
inferred← citeshttps://doi.org/10.1137/100785260openalex-snapshot
The Intersection of Two Halfspaces Has High Threshold Degree
inferred← citeshttps://doi.org/10.1137/100811623openalex-snapshot
Pseudorandom Generators for Polynomial Threshold Functions
inferred← citeshttps://doi.org/10.1137/15m1015704openalex-snapshot
Breaking the Minsky--Papert Barrier for Constant-Depth Circuits
inferred← citeshttps://doi.org/10.1137/16m1064477openalex-snapshot
The Power of Asymmetry in Constant-Depth Circuits
inferred← citeshttps://doi.org/10.1137/19m1257792openalex-snapshot
Polynomial Threshold Functions, Hyperplane Arrangements, and Random Tensors
inferred← citeshttps://doi.org/10.1137/19m1276467openalex-snapshot
A Fixed-Depth Size-Hierarchy Theorem for $\mathrm{AC}^0[\oplus]$ via the Coin Problem
inferred← citeshttps://doi.org/10.1137/20m1312459openalex-snapshot
Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC$^0$
inferred← citeshttps://doi.org/10.1137/s0097539702415317openalex-snapshot
On the Autoreducibility of Random Sequences
inferred← citeshttps://doi.org/10.1145/1250790.1250834openalex-snapshot
Separating AC 0 from depth-2 majority circuits
inferred← citeshttps://doi.org/10.1145/1490270.1490273openalex-snapshot
A Simple Proof of Bazzi’s Theorem
inferred← citeshttps://doi.org/10.1145/2090236.2090273openalex-snapshot
On beating the hybrid argument
inferred← citeshttps://doi.org/10.1145/2213977.2214044openalex-snapshot
Making polynomials robust to noise
inferred← citeshttps://doi.org/10.1145/2488608.2488610openalex-snapshot
A PRG for lipschitz functions of polynomials with applications to sparsest cut
inferred← citeshttps://doi.org/10.1145/2591796.2591858openalex-snapshot
New algorithms and lower bounds for circuits with linear threshold gates
inferred← citeshttps://doi.org/10.1145/2591796.2591871openalex-snapshot
Breaking the minsky-papert barrier for constant-depth circuits
inferred← citeshttps://doi.org/10.1145/2688073.2688108openalex-snapshot
Restricted Distribution Automatizability in PAC-Semantics
inferred← citeshttps://doi.org/10.1145/2897518.2897520openalex-snapshot
Complexity theoretic limitations on learning halfspaces
inferred← citeshttps://doi.org/10.1145/3055399.3055425openalex-snapshot
Addition is exponentially harder than counting for shallow monotone circuits
inferred← citeshttps://doi.org/10.1145/3313276.3316339openalex-snapshot
A fixed-depth size-hierarchy theorem for AC 0 [⊕] via the coin problem
inferred← citeshttps://doi.org/10.1145/3313276.3316408openalex-snapshot
Near-optimal lower bounds on the threshold degree and sign-rank of AC 0
inferred← citeshttps://doi.org/10.1145/3357713.3384328openalex-snapshot
A robust version of Hegedus’s lemma, with applications
inferred← citeshttps://doi.org/10.1145/3402926openalex-snapshot
Deterministic APSP, Orthogonal Vectors, and More
inferred← citeshttps://doi.org/10.1145/3519935.3520000openalex-snapshot
The approximate degree of DNF and CNF formulas
inferred← citeshttps://doi.org/10.1145/3618260.3649633openalex-snapshot
Detecting Low-Degree Truncation
inferred← citeshttps://doi.org/10.1145/780542.780592openalex-snapshot
New degree bounds for polynomial threshold functions
inferred← citeshttps://doi.org/10.14708/cm.v51i2.5318openalex-snapshot
The hat problem on a union of disjoint graphs
inferred← citeshttps://doi.org/10.1561/0400000033openalex-snapshot
On the Power of Small-Depth Computation
inferred← citeshttps://doi.org/10.1561/9781601983015openalex-snapshot
On the Power of Small-Depth Computation
inferred← citeshttps://doi.org/10.37236/10600openalex-snapshot
Covering Symmetric Sets of the Boolean Cube by Affine Hyperplanes
inferred← citeshttps://doi.org/10.4213/mzm8734openalex-snapshot
Небольшое уменьшение степени многочлена с заданной знаковой функцией может экспоненциально увеличить его вес и длину
inferred← citeshttps://doi.org/10.4230/lipics-approx/random.2021.42openalex-snapshot
On the probabilistic degree of an n-variate boolean function
inferred← citeshttps://doi.org/10.4230/lipics.approx/random.2022.26openalex-snapshot
Lifting with Inner Functions of Polynomial Discrepancy
inferred← citeshttps://doi.org/10.4230/lipics.ccc.2016.1openalex-snapshot
Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits
inferred← citeshttps://doi.org/10.4230/lipics.fsttcs.2012.36openalex-snapshot
Certifying polynomials for AC^0(parity) circuits, with applications
inferred← citeshttps://doi.org/10.4230/lipics.icalp.2019.30openalex-snapshot
Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC^0
inferred← citeshttps://doi.org/10.4230/lipics.itcs.2025.3openalex-snapshot
Anti-concentration for polynomials of independent random variables
inferred← citeshttps://doi.org/10.4230/lipics.tqc.2020.1openalex-snapshot
Exponential Quantum Communication Reductions from Generalizations of the Boolean Hidden Matching Problem
inferred← citeshttps://doi.org/10.46298/theoretics.23.5openalex-snapshot
A Robust Version of Heged\H{u}s's Lemma, with Applications
inferred← citeshttps://doi.org/10.48550/arxiv.0805.2135openalex-snapshot
Communication Lower Bounds Using Dual Polynomials
inferred← citeshttps://doi.org/10.48550/arxiv.0909.4727openalex-snapshot
A regularity lemma, and low-weight approximators, for low-degree polynomial threshold functions
inferred← citeshttps://doi.org/10.48550/arxiv.0910.4122openalex-snapshot
Pseudorandom Generators for Polynomial Threshold Functions
inferred← citeshttps://doi.org/10.48550/arxiv.0911.3389openalex-snapshot
Bounded Independence Fools Degree-2 Threshold Functions
inferred← citeshttps://doi.org/10.48550/arxiv.1207.2171openalex-snapshot
Relationship between circuit complexity and symmetry
inferred← citeshttps://doi.org/10.48550/arxiv.1307.1157openalex-snapshot
Representing Boolean Functions Using Polynomials: More Can Offer Less
inferred← citeshttps://doi.org/10.48550/arxiv.1401.2444openalex-snapshot
New algorithms and lower bounds for circuits with linear threshold gates
inferred← citeshttps://doi.org/10.48550/arxiv.1505.05800openalex-snapshot
Complexity Theoretic Limitations on Learning Halfspaces
inferred← citeshttps://doi.org/10.48550/arxiv.1511.08245openalex-snapshot
Shattered Sets and the Hilbert Function
inferred← citeshttps://doi.org/10.48550/arxiv.1704.03176openalex-snapshot
On the Spectral Properties of Symmetric Functions
inferred← citeshttps://doi.org/10.48550/arxiv.cs/0504048openalex-snapshot
Oracles Are Subtle But Not Malicious
inferred← citeshttps://doi.org/10.5860/choice.51-6226openalex-snapshot
The mathematics of coordinated inference: a study of generalized hat problems
inferred← citeshttps://doi.org/10.7282/t35d8qvqopenalex-snapshot
On circuit complexity classes and iterated matrix multiplication
inferred← citeshttps://doi.org/10.7494/opmath.2012.32.2.285openalex-snapshot
On the hat problem on a graph
Editorial review for independent work. ICSAC — the Institute for Complexity
Science and Advanced Computing — runs a structured editorial panel for researchers
publishing outside journals, and publishes on CiteStamp rails. Submission is free
and goes through ORCID: icsacinstitute.org/submit.