Learning the Coefficients: A Presentable Version of Border Complexity and Applications to Circuit Factoring
Abstract
References
Index Terms
- Learning the Coefficients: A Presentable Version of Border Complexity and Applications to Circuit Factoring
Recommendations
Bootstrapping variables in algebraic circuits
STOC 2018: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of ComputingWe show that for the blackbox polynomial identity testing (PIT) problem it suffices to study circuits that depend only on the first extremely few variables. One only need to consider size-s degree-s circuits that depend on the first log∘ c s variables (...
Real -Conjecture for Sum-of-Squares: A Unified Approach to Lower Bound and Derandomization
Computer Science – Theory and ApplicationsAbstractKoiran’s real -conjecture asserts that if a non-zero real univariate polynomial f can be written as , where each contains at most t monomials, then the number of distinct real roots of f is polynomially bounded in kmt. Assuming ...
Discovering the roots: uniform closure results for algebraic classes under factoring
STOC 2018: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of ComputingNewton iteration (NI) is an almost 350 years old recursive formula that approximates a simple root of a polynomial quite rapidly. We generalize it to a matrix recurrence (allRootsNI) that approximates all the roots simultaneously. In this form, the ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
- General Chairs:
- Bojan Mohar,
- Igor Shinkar,
- Program Chair:
- Ryan O'Donnell
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Check for updates
Author Tags
Qualifiers
- Research-article
Conference
Acceptance Rates
Upcoming Conference
- Sponsor:
- sigact
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 131Total Downloads
- Downloads (Last 12 months)131
- Downloads (Last 6 weeks)29
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in