×

Found 15 Documents (Results 1–15)

Sylvester-Gallai type theorems for quadratic polynomials. (English) Zbl 1434.68162

Charikar, Moses (ed.) et al., Proceedings of the 51st annual ACM SIGACT symposium on theory of computing, STOC ’19, Phoenix, AZ, USA, June 23–26, 2019. New York, NY: Association for Computing Machinery (ACM). 1203-1214 (2019).
PDFBibTeX XMLCite
Full Text: DOI arXiv

A PSPACE construction of a hitting set for the closure of small algebraic circuits. (English) Zbl 1428.68171

Diakonikolas, Ilias (ed.) et al., Proceedings of the 50th annual ACM SIGACT symposium on theory of computing, STOC ’18, Los Angeles, CA, USA, June 25–29, 2018. New York, NY: Association for Computing Machinery (ACM). 1180-1192 (2018).
MSC:  68Q25 68Q06
PDFBibTeX XMLCite
Full Text: DOI arXiv

Succinct hitting sets and barriers to proving algebraic circuits lower bounds. (English) Zbl 1369.68240

Hatami, Hamed (ed.) et al., Proceedings of the 49th annual ACM SIGACT symposium on theory of computing, STOC ’17, Montreal, QC, Canada, June 19–23, 2017. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-4528-6). 653-664 (2017).
MSC:  68Q25 68Q17 68W20
PDFBibTeX XMLCite
Full Text: DOI arXiv

Identity testing and lower bounds for read-\(k\) oblivious algebraic branching programs. (English) Zbl 1380.68175

Raz, Ran (ed.), 31st conference on computational complexity, CCC’16, Tokyo, Japan, May 29 – June 1, 2016. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-008-8). LIPIcs – Leibniz International Proceedings in Informatics 50, Article 30, 25 p. (2016).
MSC:  68Q05 68P05 68Q17 68Q25 68W20
PDFBibTeX XMLCite
Full Text: DOI arXiv

Subexponential size hitting sets for bounded depth multilinear formulas. (English) Zbl 1388.68132

Zuckerman, David (ed.), 30th conference on computational complexity, CCC’15, Portland, OR, USA, June 17–19, 2015. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-81-1). LIPIcs – Leibniz International Proceedings in Informatics 33, 304-322 (2015).
MSC:  68Q25 68Q05 68Q17 68W20 94C10
PDFBibTeX XMLCite
Full Text: DOI arXiv

Filter Results by …

Document Type

all top 5

Year of Publication

all top 3

Main Field