×

Found 37 Documents (Results 1–37)

Weak lower bounds on resource-bounded compression imply strong separations of complexity classes. (English) Zbl 1434.68160

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). 1215-1225 (2019).
PDFBibTeX XMLCite
Full Text: DOI Link

An equivalence class for orthogonal vectors. (English) Zbl 1431.68046

Chan, Timothy M. (ed.), Proceedings of the 30th annual ACM-SIAM symposium on discrete algorithms, SODA 2019, San Diego, CA, USA, January 6–9, 2019. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 21-40 (2019).
PDFBibTeX XMLCite
Full Text: DOI arXiv

Limits on representing Boolean functions by linear combinations of simple functions: thresholds, ReLUs, and low-degree polynomials. (English) Zbl 1441.68047

Servedio, Rocco A. (ed.), 33rd computational complexity conference, CCC 2018, June 22–24, 2018, San Diego, California, USA. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 102, Article 6, 24 p. (2018).
MSC:  68Q06 68Q17
PDFBibTeX XMLCite
Full Text: DOI arXiv

Counting solutions to polynomial systems via reductions. (English) Zbl 1433.68161

Seidel, Raimund (ed.), 1st symposium on simplicity in algorithms. SOSA 2018, January 7–10, 2018, New Orleans, LA, USA. Co-located with the 29th ACM-SIAM symposium on discrete algorithms (SODA 2018). Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. OASIcs – OpenAccess Ser. Inform. 61, Article 6, 15 p. (2018).
PDFBibTeX XMLCite
Full Text: DOI

Circuit lower bounds for nondeterministic quasi-polytime: an easy witness lemma for NP and NQP. (English) Zbl 1428.68172

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). 890-901 (2018).
PDFBibTeX XMLCite
Full Text: DOI

On the difference between closest, furthest, and orthogonal pairs: nearly-linear vs barely-subquadratic complexity. (English) Zbl 1403.68321

Czumaj, Artur (ed.), Proceedings of the 29th annual ACM-SIAM symposium on discrete algorithms, SODA 2018, New Orleans, LA, USA, January 7–10, 2018. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-61197-503-1/ebook). 1207-1215 (2018).
MSC:  68U05 68Q25
PDFBibTeX XMLCite
Full Text: arXiv Link

Strong ETH breaks with Merlin and Arthur: short non-interactive proofs of batch evaluation. (English) Zbl 1380.68234

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 2, 17 p. (2016).
MSC:  68Q25 03F20 68Q05 68Q10 68Q17
PDFBibTeX XMLCite
Full Text: DOI arXiv

Super-linear gate and super-quadratic wire lower bounds for depth-two and depth-three threshold circuits. (English) Zbl 1373.68220

Wichs, Daniel (ed.) et al., Proceedings of the 48th annual ACM SIGACT symposium on theory of computing, STOC ’16, Cambridge, MA, USA, June 19–21, 2016. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-4132-5). 633-643 (2016).
MSC:  68Q05 68Q17 94C10
PDFBibTeX XMLCite
Full Text: DOI arXiv

Simulating branching programs with edit distance and friends: or: a polylog shaved is a lower bound made. (English) Zbl 1373.68233

Wichs, Daniel (ed.) et al., Proceedings of the 48th annual ACM SIGACT symposium on theory of computing, STOC ’16, Cambridge, MA, USA, June 19–21, 2016. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-4132-5). 375-388 (2016).
MSC:  68Q17 68Q25
PDFBibTeX XMLCite
Full Text: DOI arXiv

More applications of the polynomial method to algorithm design. (English) Zbl 1372.68282

Indyk, Piotr (ed.), Proceedings of the 26th annual ACM-SIAM symposium on discrete algorithms, SODA 2015, Portland, San Diego, CA, January 4–6, 2015. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-61197-374-7; 978-1-61197-373-0/ebook). 218-230 (2015).
PDFBibTeX XMLCite
Full Text: DOI

Thinking algorithmically about impossibility (invited talk). (English) Zbl 1373.68245

Kreutzer, Stephan (ed.), 24th EACSL annual conference and 29th workshop on computer science logic, CSL’15, Berlin, Germany, September 7–10, 2015. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-90-3). LIPIcs – Leibniz International Proceedings in Informatics 41, 14-23 (2015).
PDFBibTeX XMLCite
Full Text: DOI

The circuit-input game, natural proofs, and testing circuits with data. (English) Zbl 1364.68193

Proceedings of the 6th conference on innovations in theoretical computer science, ITCS’15, Rehovot, Israel, January 11–13, 2015. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3333-7). 263-270 (2015).
MSC:  68Q05 68Q15 68Q17 91A80 94C10 94C12
PDFBibTeX XMLCite
Full Text: DOI

Algorithms for circuits and circuits for algorithms: connecting the tractable and intractable. (English) Zbl 1373.68246

Jang, Sun Young (ed.) et al., Proceedings of the International Congress of Mathematicians (ICM 2014), Seoul, Korea, August 13–21, 2014. Vol. IV: Invited lectures. Seoul: KM Kyung Moon Sa (ISBN 978-89-6105-807-0/hbk; 978-89-6105-803-2/set). 659-682 (2014).
MSC:  68Q17 68Q25
PDFBibTeX XMLCite

New algorithms and lower bounds for circuits with linear threshold gates. (English) Zbl 1315.68142

Proceedings of the 46th annual ACM symposium on theory of computing, STOC ’14, New York, NY, USA, May 31 – June 3, 2014. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-2710-7). 194-202 (2014).
MSC:  68Q17 68Q15 68W05 94C10
PDFBibTeX XMLCite
Full Text: DOI arXiv

Natural proofs versus derandomization. (English) Zbl 1293.68135

Proceedings of the 45th annual ACM symposium on theory of computing, STOC ’13. Palo Alto, CA, USA, June 1–4, 2013. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-2029-0). 21-30 (2013).
MSC:  68Q15 03F20 68Q17 94C10
PDFBibTeX XMLCite
Full Text: DOI arXiv

Towards NEXP versus BPP? (English) Zbl 1381.68092

Bulatov, Andrei A. (ed.) et al., Computer science – theory and applications. 8th international computer science symposium in Russia, CSR 2013, Ekaterinburg, Russia, June 25–29, 2013. Proceedings. Berlin: Springer (ISBN 978-3-642-38535-3/pbk). Lecture Notes in Computer Science 7913, 174-182 (2013).
MSC:  68Q15 68Q17
PDFBibTeX XMLCite
Full Text: DOI

Improving exhaustive search implies superpolynomial lower bounds. (English) Zbl 1293.68177

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). 231-240 (2010).
MSC:  68Q25 68Q15 68Q17
PDFBibTeX XMLCite
Full Text: DOI

On the possibility of faster SAT algorithms. (English) Zbl 1288.68135

Charikar, Moses (ed.), Proceedings of the 21st annual ACM-SIAM symposium on discrete algorithms, SODA 2010, Austin, TX, USA, January 17–19, 2010. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM) (ISBN 978-0-89871-698-6/CD-ROM). 1065-1075 (2010).
PDFBibTeX XMLCite

Resolving the complexity of some data privacy problems. (English) Zbl 1288.68058

Abramsky, Samson (ed.) et al., Automata, languages and programming. 37th international colloquium, ICALP 2010, Bordeaux, France, July 6–10, 2010. Proceedings, Part II. Berlin: Springer (ISBN 978-3-642-14161-4/pbk). Lecture Notes in Computer Science 6199, 393-404 (2010).
MSC:  68P15 68Q17 68Q25
PDFBibTeX XMLCite
Full Text: DOI arXiv

An improved time-space lower bound for tautologies. (English) Zbl 1248.03078

Ngo, Hung Q. (ed.), Computing and combinatorics. 15th annual international conference, COCOON 2009, Niagara Falls, NY, USA, July 13–15, 2009. Proceedings. Berlin: Springer (ISBN 978-3-642-02881-6/pbk). Lecture Notes in Computer Science 5609, 429-438 (2009).
MSC:  03F20 68Q17
PDFBibTeX XMLCite
Full Text: DOI

Confronting hardness using a hybrid approach. (English) Zbl 1192.68381

Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, Miami, FL, January 22–24, 2006. New York, NY: Association for Computing Machinery (ACM); Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM) (ISBN 0-89871-605-5). 1-10 (2006).
MSC:  68Q25 68Q17
PDFBibTeX XMLCite
Full Text: DOI

Filter Results by …

Document Type

all top 5

Year of Publication

all top 3

Main Field

Software