Polynomial representations of threshold functions and algorithmic applications

DOI10.1109/FOCS.2016.57MaRDI QIDQ6946451zbMATH OpenFDO

Authors Timothy M. Chan, Josh Alman, Ryan Williams

Publication date 6 August 2025

Full work available at URL https://doi.org/10.1109/FOCS.2016.57

Mathematics Subject Classification ID

Theory of computing (68Qxx) Discrete mathematics in relation to computer science (68Rxx) Algorithms in computer science (68Wxx)

Cited in

(6)

• Finer-grained reductions in fine-grained hardness of approximation
• Efficient construction of rigid matrices using an NP oracle
• Counting short vector pairs by inner product and relations to the permanent
• Majority vs. approximate linear sum and average-case complexity below NC^1
• \#SAT-algorithms for classes of threshold circuits based on probabilistic rank
• Kronecker products, low-depth circuits, and matrix rigidity

This page was built for publication: Polynomial representations of threshold functions and algorithmic applications

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6946451)