×

Found 11 Documents (Results 1–11)

Approximating the number of prime factors given an oracle to Euler’s totient function. (English) Zbl 07799595

Bojańczyk, Mikołaj (ed.) et al., 41st IARCS annual conference on foundations of software technology and theoretical computer science, FSTTCS 2021, virtual conference, December 15–17, 2021. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 213, Article 17, 10 p. (2021).
MSC:  68N30 68Qxx
PDFBibTeX XMLCite
Full Text: DOI

Reconstruction algorithms for low-rank tensors and depth-3 multilinear circuits. (English) Zbl 07765212

Khuller, Samir (ed.) et al., Proceedings of the 53rd annual ACM SIGACT symposium on theory of computing, STOC ’21, virtual, Italy, June 21–25, 2021. New York, NY: Association for Computing Machinery (ACM). 809-822 (2021).
MSC:  68Qxx
PDFBibTeX XMLCite
Full Text: DOI arXiv

On some computations on sparse polynomials. (English) Zbl 1470.68043

Jansen, Klaus (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 20th international workshop, APPROX 2017 and 21st international workshop, RANDOM 2017, Berkeley, CA, USA, August 16–18, 2017. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 81, Article 48, 21 p. (2017).
MSC:  68Q06 68W20
PDFBibTeX XMLCite
Full Text: DOI

Complete derandomization of identity testing and reconstruction of read-once formulas. (English) Zbl 1440.68329

O’Donnell, Ryan (ed.), 32nd computational complexity conference, CCC 2017, July 6–9, 2017, Riga, Latvia. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 79, Article 32, 13 p. (2017).
MSC:  68W20 68Q06 68W40
PDFBibTeX XMLCite
Full Text: DOI

Deterministically factoring sparse polynomials into multilinear factors and sums of univariate polynomials. (English) Zbl 1375.68228

Garg, Naveen (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. Proceedings of the 18th international workshop on approximation algorithms for combinatorial optimization problems (APPROX 2015) and the 19th international workshop on randomization and computation (RANDOM 2015), Princeton, NJ, USA, August 24–26, 2015. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-89-7). LIPIcs – Leibniz International Proceedings in Informatics 40, 943-958 (2015).
MSC:  68W30 12E05 12Y05 68Q25
PDFBibTeX XMLCite
Full Text: DOI

Black-box identity testing of depth-4 multilinear circuits. (English) Zbl 1288.68137

Proceedings of the 43rd annual ACM symposium on theory of computing, STOC ’11. San Jose, CA, USA, June 6–8, 2011. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-0691-1). 421-430 (2011).
MSC:  68Q25 12Y05 94C10
PDFBibTeX XMLCite
Full Text: DOI

Deterministic identity testing of depth-\(4\) multilinear circuits with bounded top fan-in. (English) Zbl 1293.90040

Proceedings of the 42nd annual ACM symposium on theory of computing, STOC ’10. Cambridge, MA, USA, June 5–8, 2010. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-60558-817-9). 649-658 (2010).
MSC:  90C05
PDFBibTeX XMLCite
Full Text: DOI

Filter Results by …

Document Type

all top 5

Year of Publication

all top 3

Main Field