×

Found 73 Documents (Results 1–73)

Black-box hypotheses and lower bounds. (English) Zbl 07724202

Bonchi, Filippo (ed.) et al., 46th international symposium on mathematical foundations of computer science, MFCS 2021, August 23–27, 2021, Tallinn, Estonia. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 202, Article 29, 22 p. (2021).
MSC:  68Qxx
PDFBibTeX XMLCite
Full Text: DOI

Lower bounds against sparse symmetric functions of ACC circuits: expanding the reach of #SAT algorithms. (English) Zbl 07650944

Paul, Christophe (ed.) et al., 37th international symposium on theoretical aspects of computer science, STACS 2020, Montpellier, France, March 10–13, 2020. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 154, Article 59, 17 p. (2020).
MSC:  68Qxx
PDFBibTeX XMLCite
Full Text: DOI arXiv

Relations and equivalences between circuit lower bounds and Karp-Lipton theorems. (English) Zbl 07564430

Shpilka, Amir (ed.), 34th computational complexity conference, CCC 2019, New Brunswick, NJ, USA, July 18–20, 2019. Proceedings. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 137, Article 30, 21 p. (2019).
MSC:  68Q25
PDFBibTeX XMLCite
Full Text: DOI

Stronger connections between circuit analysis and circuit lower bounds, via PCPs of proximity. (English) Zbl 07564419

Shpilka, Amir (ed.), 34th computational complexity conference, CCC 2019, New Brunswick, NJ, USA, July 18–20, 2019. Proceedings. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 137, Article 19, 43 p. (2019).
MSC:  68Q25
PDFBibTeX XMLCite
Full Text: DOI

Quadratic time-space lower bounds for computing natural functions with a random oracle. (English) Zbl 07559099

Blum, Avrim (ed.), 10th innovations in theoretical computer science conference, ITCS 2019, January 10–12, 2019, San Diego, CA, USA. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 124, Article 56, 20 p. (2019).
MSC:  68Qxx
PDFBibTeX XMLCite
Full Text: DOI

The orthogonal vectors conjecture for branching programs and formulas. (English) Zbl 07559091

Blum, Avrim (ed.), 10th innovations in theoretical computer science conference, ITCS 2019, January 10–12, 2019, San Diego, CA, USA. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 124, Article 48, 15 p. (2019).
MSC:  68Qxx
PDFBibTeX XMLCite
Full Text: DOI arXiv

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

Generalized Kakeya sets for polynomial evaluation and faster computation of fermionants. (English) Zbl 1443.68043

Lokshtanov, Daniel (ed.) et al., 12th international symposium on parameterized and exact computation, IPEC 2017, Vienna, Austria, September 6–8, 2017. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 89, Article 6, 13 p. (2018).
PDFBibTeX XMLCite
Full Text: DOI

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

Easiness amplification and uniform circuit lower bounds. (English) Zbl 1440.68129

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 8, 21 p. (2017).
MSC:  68Q25 68Q06
PDFBibTeX XMLCite
Full Text: DOI

Beating brute force for systems of polynomial equations over finite fields. (English) Zbl 1433.11135

Klein, Philip N. (ed.), Proceedings of the 28th annual ACM-SIAM symposium on discrete algorithms, SODA 2017, Barcelona, Spain, January 16–19, 2017. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 2190-2202 (2017).
MSC:  11T06 11Y16
PDFBibTeX XMLCite
Full Text: DOI

Faster online matrix-vector multiplication. (English) Zbl 1410.68409

Klein, Philip N. (ed.), Proceedings of the 28th annual ACM-SIAM symposium on discrete algorithms, SODA 2017, Barcelona, Spain, January 16–19, 2017. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 2182-2189 (2017).
MSC:  68W27 15B34 65F30 68P05 68Q25 68W20
PDFBibTeX XMLCite
Full Text: DOI arXiv

Deterministic APSP, orthogonal vectors, and more: quickly derandomizing Razborov-Smolensky. (English) Zbl 1410.68286

Krauthgamer, Robert (ed.), Proceedings of the 27th annual ACM-SIAM symposium on discrete algorithms, SODA 2016, Arlington, VA, USA, January 10–12, 2016. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 1246-1255 (2016).
PDFBibTeX XMLCite
Full Text: DOI

Deterministic time-space trade-offs for \(k\)-SUM. (English) Zbl 1388.68127

Chatzigiannakis, Ioannis (ed.) et al., 43rd international colloquium on automata, languages, and programming, ICALP 2016, Rome, Italy, July 12–15, 2016. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-013-2). LIPIcs – Leibniz International Proceedings in Informatics 55, Article 58, 14 p. (2016).
MSC:  68Q25
PDFBibTeX XMLCite
Full Text: DOI arXiv

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

Finding four-node subgraphs in triangle time. (English) Zbl 1371.05292

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). 1671-1680 (2015).
MSC:  05C85 68Q25
PDFBibTeX XMLCite
Full Text: DOI

Beating exhaustive search for quantified Boolean formulas and connections to circuit complexity. (English) Zbl 1371.68123

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). 231-241 (2015).
MSC:  68Q25 68Q15 68W20 94C10
PDFBibTeX XMLCite
Full Text: DOI

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

The polynomial method in circuit complexity applied to algorithm design (invited talk). (English) Zbl 1436.68392

Raman, Venkatesh (ed.) et al., 34th international conference on foundation of software technology and theoretical computer science, FSTTCS 2014, New Delhi, India, December 15–17, 2014. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 29, 47-60 (2014).
MSC:  68W01 68Q06
PDFBibTeX XMLCite
Full Text: DOI

Faster decision of first-order graph properties. (English) Zbl 1394.68192

Proceedings of the joint meeting of the twenty-third EACSL annual conference on computer science logic, CSL, and the 2014 29th annual ACM/IEEE symposium on logic in computer science, LICS 2014, Vienna, Austria, July 14–18, 2014. Los Alamitos, CA: IEEE Computer Society (ISBN 978-1-4503-2886-9). Paper No. 80, 6 p. (2014).
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

Improved parameterized algorithms for above average constraint satisfaction. (English) Zbl 1352.68115

Marx, Dániel (ed.) et al., Parameterized and exact computation. 6th international symposium, IPEC 2011, Saarbrücken, Germany, September 6–8, 2011. Revised selected papers. Berlin: Springer (ISBN 978-3-642-28049-8/pbk). Lecture Notes in Computer Science 7112, 118-131 (2012).
MSC:  68Q25 68T20 68W40
PDFBibTeX XMLCite
Full Text: DOI arXiv

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

Regularity lemmas and combinatorial algorithms. (English) Zbl 1292.05242

2009 IEEE 50th annual symposium on foundations of computer science – FOCS 2009. Proceedings of the symposium, Atlanta, GA, USA, October 24–27, 2009. Los Alamitos, CA: IEEE Computer Society (ISBN 978-0-7695-3850-1; 978-1-4244-5116-6/ebook). 745-754 (2009).
PDFBibTeX XMLCite
Full Text: DOI

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

Limits and applications of group algebras for parameterized problems. (English) Zbl 1248.68251

Albers, Susanne (ed.) et al., Automata, languages and programming. 36th international colloquium, ICALP 2009, Rhodes, Greece, July 5–12, 2009. Proceedings, Part I. Berlin: Springer (ISBN 978-3-642-02926-4/pbk). Lecture Notes in Computer Science 5555, 653-664 (2009).
MSC:  68Q25 68W20
PDFBibTeX XMLCite
Full Text: DOI Link

Matrix-vector multiplication in sub-quadratic time (some preprocessing required). (English) Zbl 1302.65111

Proceedings of the eighteenth annual ACM-SIAM symposium on discrete algorithms, SODA 2007, New Orleans, LA, USA, January 7–9, 2007. New York, NY: Association for Computing Machinery (ACM); Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM) (ISBN 978-0-89871-624-5). 995-1001 (2007).
MSC:  65F30 65Y20 68Q25
PDFBibTeX XMLCite

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

Finding the smallest \(H\)-subgraph in real weighted graphs and related problems. (English) Zbl 1223.05302

Bugliesi, Michele (ed.) et al., Automata, languages and programming. 33rd international colloquium, ICALP 2006, Venice, Italy, July 10–14, 2006. Proceedings, Part I. Berlin: Springer (ISBN 978-3-540-35904-3/pbk). Lecture Notes in Computer Science 4051, 262-273 (2006).
MSC:  05C85 05C22 68Q25
PDFBibTeX XMLCite
Full Text: DOI

On computing \(k\)-CNF formula properties. (English) Zbl 1204.68212

Giunchiglia, Enrico (ed.) et al., Theory and applications of satisfiability testing. 6th international conference, SAT 2003, Santa Margherita Ligure, Italy, May 5–8, 2003. Selected revised papers. Berlin: Springer (ISBN 3-540-20851-8/pbk). Lect. Notes Comput. Sci. 2919, 330-340 (2004).
PDFBibTeX XMLCite
Full Text: DOI

A new algorithm for optimal constraint satisfaction and its implications. (English) Zbl 1098.68120

Díaz, Josep (ed.) et al., Automata, languages and programming. 31st international colloquium, ICALP 2004, Turku, Finland, July 12–16, 2004. Proceedings. Berlin: Springer (ISBN 3-540-22849-7/pbk). Lecture Notes in Computer Science 3142, 1227-1237 (2004).
MSC:  68T20 68Q25
PDFBibTeX XMLCite
Full Text: DOI

Filter Results by …

Document Type

all top 5

Year of Publication

all top 3

Main Field