×

Found 287 Documents (Results 1–100)

Communication and information complexity. (English) Zbl 07822678

Beliaev, Dmitry (ed.) et al., International congress of mathematicians 2022, ICM 2022, Helsinki, Finland, virtual, July 6–14, 2022. Volume 1. Prize lectures. Berlin: European Mathematical Society (EMS). 284-320 (2023).
MSC:  68Q11 68P30 94A15
PDFBibTeX XMLCite
Full Text: DOI

The work of Mark Braverman. (English) Zbl 07822670

Beliaev, Dmitry (ed.) et al., International congress of mathematicians 2022, ICM 2022, Helsinki, Finland, virtual, July 6–14, 2022. Volume 1. Prize lectures. Berlin: European Mathematical Society (EMS). 106-117 (2023).
PDFBibTeX XMLCite
Full Text: DOI

The communication complexity of functions with large outputs. (English) Zbl 07786530

Rajsbaum, Sergio (ed.) et al., Structural information and communication complexity. 30th international colloquium, SIROCCO 2023, Alcalá de Henares, Spain, June 6–9, 2023. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13892, 427-458 (2023).
MSC:  68Mxx 68Q11 68R10
PDFBibTeX XMLCite
Full Text: DOI arXiv

Simultaneous contests with equal sharing allocation of prizes: computational complexity and price of anarchy. (English) Zbl 1520.91014

Kanellopoulos, Panagiotis (ed.) et al., Algorithmic game theory. 15th international symposium, SAGT 2022, Colchester, UK, September 12–15, 2022. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13584, 133-150 (2022).
MSC:  91A10 91A68 68Q17
PDFBibTeX XMLCite
Full Text: DOI arXiv

Discrete versions of the KKM lemma and their PPAD-completeness. (English) Zbl 07615737

Kulikov, Alexander S. (ed.) et al., Computer science – theory and applications. 17th international computer science symposium in Russia, CSR 2022, virtual event, June 29 – July 1, 2022. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13296, 170-189 (2022).
MSC:  68Qxx
PDFBibTeX XMLCite
Full Text: DOI

Dichotomy result on 3-regular bipartite non-negative functions. (English) Zbl 07493526

Santhanam, Rahul (ed.) et al., Computer science – theory and applications. 16th international computer science symposium in Russia, CSR 2021, Sochi, Russia, June 28 – July 2, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12730, 102-115 (2021).
MSC:  68Qxx
PDFBibTeX XMLCite
Full Text: DOI arXiv

Almost optimal distribution-free sample-based testing of \(k\)-modality. (English) Zbl 07758329

Byrka, Jarosław (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 23rd international conference, APPROX 2020, and 24th international conference, RANDOM 2020, August 17–19, 2020, Virtual conference. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 176, Article 27, 19 p. (2020).
MSC:  68W20 68W25 90C27
PDFBibTeX XMLCite
Full Text: DOI

Vector-matrix-vector queries for solving linear algebra, statistics, and graph problems. (English) Zbl 07758328

Byrka, Jarosław (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 23rd international conference, APPROX 2020, and 24th international conference, RANDOM 2020, August 17–19, 2020, Virtual conference. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 176, Article 26, 20 p. (2020).
MSC:  68W20 68W25 90C27
PDFBibTeX XMLCite
Full Text: DOI arXiv

On testing and robust characterizations of convexity. (English) Zbl 07758320

Byrka, Jarosław (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 23rd international conference, APPROX 2020, and 24th international conference, RANDOM 2020, August 17–19, 2020, Virtual conference. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 176, Article 18, 15 p. (2020).
MSC:  68W20 68W25 90C27
PDFBibTeX XMLCite
Full Text: DOI

Almost optimal testers for concise representations. (English) Zbl 07758307

Byrka, Jarosław (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 23rd international conference, APPROX 2020, and 24th international conference, RANDOM 2020, August 17–19, 2020, Virtual conference. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 176, Article 5, 20 p. (2020).
MSC:  68W20 68W25 90C27
PDFBibTeX XMLCite
Full Text: DOI arXiv

Optimal polynomial-time compression for Boolean max CSP. (English) Zbl 07651202

Grandoni, Fabrizio (ed.) et al., 28th annual European symposium on algorithms. ESA 2020, September 7–9, 2020, Pisa, Italy, virtual conference. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 173, Article 63, 19 p. (2020).
MSC:  68Wxx
PDFBibTeX XMLCite
Full Text: DOI arXiv

A super-quadratic lower bound for depth four arithmetic circuits. (English) Zbl 07561751

Saraf, Shubhangi (ed.), 35th computational complexity conference, CCC 2020, July 28–31, 2020, Saarbrücken, Germany, virtual conference. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 169, Article 23, 31 p. (2020).
MSC:  68Q25
PDFBibTeX XMLCite
Full Text: DOI

Schur polynomials do not have small formulas if the determinant doesn’t. (English) Zbl 07561742

Saraf, Shubhangi (ed.), 35th computational complexity conference, CCC 2020, July 28–31, 2020, Saarbrücken, Germany, virtual conference. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 169, Article 14, 27 p. (2020).
MSC:  68Q25
PDFBibTeX XMLCite
Full Text: DOI arXiv

Approximability of the eight-vertex model. (English) Zbl 07561732

Saraf, Shubhangi (ed.), 35th computational complexity conference, CCC 2020, July 28–31, 2020, Saarbrücken, Germany, virtual conference. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 169, Article 4, 18 p. (2020).
MSC:  68Q25
PDFBibTeX XMLCite
Full Text: DOI arXiv

A quadratic lower bound for algebraic branching programs. (English) Zbl 07561730

Saraf, Shubhangi (ed.), 35th computational complexity conference, CCC 2020, July 28–31, 2020, Saarbrücken, Germany, virtual conference. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 169, Article 2, 21 p. (2020).
MSC:  68Q25
PDFBibTeX XMLCite
Full Text: DOI

Randomized polynomial-time equivalence between determinant and trace-IMM equivalence tests. (English) Zbl 07559443

Esparza, Javier (ed.) et al., 45th international symposium on mathematical foundations of computer science, MFCS 2020, August 25–26, 2020, Prague, Czech Republic. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 170, Article 72, 16 p. (2020).
MSC:  68Qxx
PDFBibTeX XMLCite
Full Text: DOI arXiv

Filter Results by …

Document Type

all top 5

Author

all top 5

Year of Publication

all top 3

Main Field

Biographic Reference