Counting Solutions to Polynomial Systems via Reductions
From MaRDI portal
Publication:5240420
DOI10.4230/OASIcs.SOSA.2018.6zbMath1433.68161OpenAlexW2782707694MaRDI QIDQ5240420
Publication date: 25 October 2019
Full work available at URL: https://dblp.uni-trier.de/db/conf/soda/sosa2018.html#Williams18a
finite fieldpolynomial equationsderandomizationcounting complexitystrong exponential time hypothesis
Analysis of algorithms and problem complexity (68Q25) Polynomials over finite fields (11T06) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Randomized algorithms (68W20) Solving polynomial systems; resultants (13P15)
Related Items
Fast exact algorithms using Hadamard product of polynomials, Unnamed Item, Efficient Construction of Rigid Matrices Using an NP Oracle
Cites Work
- Unnamed Item
- DNF sparsification and a faster deterministic counting algorithm
- Studies in complexity and cryptography. Miscellanea on the interplay between randomness and computation. In collaboration with Lidor Avigad, Mihir Bellare, Zvika Brakerski, Shafi Goldwasser, Shai Halevi, Tali Kaufman, Leonid Levin, Noam Nisan, Dana Ron, Madhu Sudan, Luca Trevisan, Salil Vadhan, Avi Wigderson, David Zuckerman
- The sum of \(D\) small-bias generators fools polynomials of degree \(D\)
- Pseudorandom bits for constant depth circuits
- Approximate inclusion-exclusion
- Approximating probability distributions using small sample spaces
- Which problems have strongly exponential complexity?
- On deterministic approximation of DNF
- A new algorithm for optimal 2-constraint satisfaction and its implications
- Exponential Time Complexity of Weighted Counting of Independent Sets
- Pseudorandom Bits for Polynomials
- Polylogarithmic independence fools AC 0 circuits
- On Tractable Exponential Sums
- The Complexity of Satisfiability of Small Depth Circuits
- Probabilistic Algorithms in Finite Fields
- Polynomial Threshold Functions, $AC^0 $ Functions, and Spectral Norms
- Simple Constructions of Almost k-wise Independent Random Variables
- Explicit Constructions of Depth-2 Majority Circuits for Comparison and Addition
- A fast deterministic algorithm for formulas that have many satisfying assignments
- Deterministic APSP, Orthogonal Vectors, and More: Quickly Derandomizing Razborov-Smolensky
- Beating Brute Force for Systems of Polynomial Equations over Finite Fields
- Parity Separation: A Scientifically Proven Method for Permanent Weight Loss
- Efficient approximation of product distributions
- Exponential Time Complexity of the Permanent and the Tutte Polynomial
- Fine-grained reductions from approximate counting to decision
- Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
- Finding Four-Node Subgraphs in Triangle Time
- Finding orthogonal vectors in discrete structures
- An FPTAS for #Knapsack and Related Counting Problems
