×

Found 367 Documents (Results 1–100)

Memory-sample lower bounds for learning with classical-quantum hybrid memory. (English) Zbl 07844657

Saha, Barna (ed.) et al., Proceedings of the 55th annual ACM SIGACT symposium on theory of computing, STOC ’23, Orlando, FL, USA, June 20–23, 2023. New York, NY: Association for Computing Machinery (ACM). 1097-1110 (2023).
MSC:  68Qxx
PDFBibTeX XMLCite
Full Text: DOI arXiv

The space complexity of sampling. (English) Zbl 07829272

Braverman, Mark (ed.), 13th innovations in theoretical computer science conference, ITCS 2022, Berkeley, CA, USA, January 31 – February 3, 2022. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 215, Article 40, 23 p. (2022).
MSC:  68Qxx
PDFBibTeX XMLCite
Full Text: DOI

The space complexity of consensus from swap. (English) Zbl 07824263

Milani, Alessia (ed.) et al., Proceedings of the 41st ACM symposium on principles of distributed computing, PODC ’22, Salerno, Italy, July 25–29, 2022. New York, NY: Association for Computing Machinery (ACM). 176-186 (2022).
MSC:  68M14 68W15
PDFBibTeX XMLCite
Full Text: DOI arXiv

Lower bounds for the number of random bits in Monte Carlo algorithms. (English) Zbl 07805183

Keller, Alexander (ed.), Monte Carlo and quasi-Monte Carlo methods. Revised papers of the 14th international conference in Monte Carlo and quasi-Monte Carlo methods in scientific computing, MCQMC 2020, Oxford, United Kingdom, August 10–14, 2020. Cham: Springer. Springer Proc. Math. Stat. 387, 131-147 (2022).
MSC:  65C05 65Y20
PDFBibTeX XMLCite
Full Text: DOI arXiv

Optimal vertex connectivity oracles. (English) Zbl 07774328

Leonardi, Stefano (ed.) et al., Proceedings of the 54th annual ACM SIGACT symposium on theory of computing, STOC ’22, Rome, Italy June 20–24, 2022. New York, NY: Association for Computing Machinery (ACM). 151-161 (2022).
MSC:  68Qxx
PDFBibTeX XMLCite
Full Text: DOI arXiv

On eigenproblem for inverted harmonic oscillators. (English) Zbl 1484.34073

Banaszak, Grzegorz (ed.) et al., Arithmetic methods in mathematical physics and biology II. Proceedings of the 2nd international conference, Będlewo, Poland, August 5–11, 2018. Warsaw: Polish Academy of Sciences, Institute of Mathematics. Banach Cent. Publ. 124, 61-73 (2021).
PDFBibTeX XMLCite
Full Text: DOI arXiv

Quadratic Euclidean 1-mean and 1-median 2-clustering problem with constraints on the size of the clusters: complexity and approximability. (English. Russian original) Zbl 1522.68654

Proc. Steklov Inst. Math. 313, Suppl. 1, S117-S124 (2021); translation from Tr. Inst. Mat. Mekh. (Ekaterinburg) 25, No. 4, 69-78 (2019).
MSC:  68U05 68Q17
PDFBibTeX XMLCite
Full Text: DOI

On the hardness of set disjointness and set intersection with bounded universe. (English) Zbl 07650240

Lu, Pinyan (ed.) et al., 30th international symposium on algorithms and computation, ISAAC 2019, Shanghai University of Finance and Economics, Shanghai, China, December 8–11, 2019. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 149, Article 7, 22 p. (2019).
MSC:  68Wxx
PDFBibTeX XMLCite
Full Text: DOI arXiv

Space-optimal naming in population protocols. (English) Zbl 1515.68060

Suomela, Jukka (ed.), 33rd international symposium on distributed computing, DISC 2019, Budapest, Hungary, October 14–18, 2019. Proceedings. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 146, Article 9, 16 p. (2019).
PDFBibTeX XMLCite
Full Text: DOI

Time-space lower bounds for two-pass learning. (English) Zbl 07564422

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 22, 39 p. (2019).
MSC:  68Q25
PDFBibTeX XMLCite
Full Text: DOI

Space lower bounds for the signal detection problem. (English) Zbl 1517.68045

Niedermeier, Rolf (ed.) et al., 36th international symposium on theoretical aspects of computer science, STACS 2019, March 13–16, 2019, Berlin, Germany. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 126, Article 26, 13 p. (2019).
MSC:  68M14 68Q17 68W15
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

Oscillation properties of a multipoint fourth-order boundary-value problem with spectral parameter in the boundary condition. (English. Russian original) Zbl 1442.34043

Math. Notes 106, No. 6, 899-903 (2019); translation from Mat. Zametki 106, No. 6, 854-859 (2019).
PDFBibTeX XMLCite
Full Text: DOI

NP-completeness of some problems of partitioning a finite set of points in Euclidean space into balanced clusters. (English. Russian original) Zbl 1437.62232

Dokl. Math. 100, No. 2, 416-419 (2019); translation from Dokl. Akad. Nauk, Ross. Akad. Nauk 488, No. 1, 16-20 (2019).
PDFBibTeX XMLCite
Full Text: DOI

Integrated bounds for disintegrated storage. (English) Zbl 1497.68035

Schmid, Ulrich (ed.) et al., 32nd international symposium on distributed computing, DISC 2018, New Orleans, Louisiana, USA, October 15–19, 2018. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 121, Article 11, 18 p. (2018).
MSC:  68M14
PDFBibTeX XMLCite
Full Text: DOI arXiv

Entropy samplers and strong generic lower bounds for space bounded learning. (English) Zbl 1462.68161

Karlin, Anna R. (ed.), 9th innovations in theoretical computer science conference, ITCS 2018, Cambridge, MA, USA, January 11–14, 2018. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 94, Article 28, 20 p. (2018).
MSC:  68T05 68Q17
PDFBibTeX XMLCite
Full Text: DOI

The \(k\)-server problem with advice in \(d\) dimensions and on the sphere. (English) Zbl 1444.68300

Tjoa, A Min (ed.) et al., SOFSEM 2018: theory and practice of computer science. 44th international conference on current trends in theory and practice of computer science, Krems, Austria, January 29 – February 2, 2018. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 10706, 396-409 (2018).
MSC:  68W27 68Q17 68U05
PDFBibTeX XMLCite
Full Text: DOI

Hardness of function composition for semantic read once branching programs. (English) Zbl 1441.68071

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 15, 22 p. (2018).
MSC:  68Q17 68P05 68Q55
PDFBibTeX XMLCite
Full Text: DOI

Brief announcement: Space-optimal naming in population protocols. (English) Zbl 1428.68366

Proceedings of the 37th ACM symposium on principles of distributed computing, PODC ’18, Egham, UK, July 23–27, 2018. New York, NY: Association for Computing Machinery (ACM). 479-481 (2018).
MSC:  68W15
PDFBibTeX XMLCite
Full Text: DOI

Revisionist simulations: a new approach to proving space lower bounds. (English) Zbl 1428.68065

Proceedings of the 37th ACM symposium on principles of distributed computing, PODC ’18, Egham, UK, July 23–27, 2018. New York, NY: Association for Computing Machinery (ACM). 61-70 (2018).
MSC:  68M14 68Q17 68W15
PDFBibTeX XMLCite
Full Text: DOI arXiv

Extractor-based time-space lower bounds for learning. (English) Zbl 1428.68238

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). 990-1002 (2018).
MSC:  68T05 68Q17
PDFBibTeX XMLCite
Full Text: DOI arXiv

Approximation scheme for the problem of weighted 2-clustering with a fixed center of one cluster. (English. Russian original) Zbl 1486.68256

Proc. Steklov Inst. Math. 303, Suppl. 1, S136-S145 (2018); translation from Tr. Inst. Mat. Mekh. (Ekaterinburg) 23, No. 3, 159-170 (2017).
PDFBibTeX XMLCite
Full Text: DOI

NP-hardness of some Euclidean problems of partitioning a finite set of points. (English. Russian original) Zbl 1393.68176

Comput. Math. Math. Phys. 58, No. 5, 822-826 (2018); translation from Zh. Vychisl. Mat. Mat. Fiz. 58, No. 5, 852-856 (2018).
MSC:  68U05 68Q17
PDFBibTeX XMLCite
Full Text: DOI

Complexity and approximation of the longest vector sum problem. (English) Zbl 1504.68267

Solis-Oba, Roberto (ed.) et al., Approximation and online algorithms. 15th international workshop, WAOA 2017, Vienna, Austria, September 7–8, 2017. Revised selected papers. Cham: Springer. Lect. Notes Comput. Sci. 10787, 41-51 (2018).
PDFBibTeX XMLCite
Full Text: DOI

Polynomial-time approximation algorithm for the problem of cardinality-weighted variance-based 2-clustering with a given center. (English. Russian original) Zbl 1478.68450

Comput. Math. Math. Phys. 58, No. 1, 130-136 (2018); translation from Zh. Vychisl. Mat. Mat. Fiz. 58, No. 1, 136-142 (2018).
PDFBibTeX XMLCite
Full Text: DOI

Orthogonal vectors indexing. (English) Zbl 1457.68116

Okamoto, Yoshio (ed.) et al., 28th international symposium on algorithms and computation, ISAAC 2017, December 9–12, 2017, Phuket, Thailand. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 92, Article 40, 12 p. (2017).
MSC:  68Q17 68P05 68Q25
PDFBibTeX XMLCite
Full Text: DOI arXiv

Time and space optimal counting in population protocols. (English) Zbl 1432.68016

Fatourou, Panagiota (ed.) et al., 20th international conference on principles of distributed systems (OPODIS 2016), Madrid, Spain, December 13–16, 2016. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 70, Article 13, 17 p. (2017).
PDFBibTeX XMLCite
Full Text: DOI arXiv

Cumulative space in black-white pebbling and resolution. (English) Zbl 1402.68079

Papadimitriou, Christos H. (ed.), 8th innovations in theoretical computer science conference, ITCS 2017, Berkeley, CA, USA, January 9–11, 2017. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-029-3). LIPIcs – Leibniz International Proceedings in Informatics 67, Article 38, 21 p. (2017).
MSC:  68Q25 03F20 68Q17
PDFBibTeX XMLCite
Full Text: DOI

An approximation algorithm for a problem of partitioning a sequence into clusters with constraints on their cardinalities. (English. Russian original) Zbl 1390.68763

Proc. Steklov Inst. Math. 299, Suppl. 1, S88-S96 (2017); translation from Tr. Inst. Mat. Mekh. (Ekaterinburg) 22, No. 3, 144-152 (2016).
MSC:  68W25 68Q17 68U05
PDFBibTeX XMLCite
Full Text: DOI

Approximation algorithm for the problem of partitioning a sequence into clusters. (English. Russian original) Zbl 1423.68596

Comput. Math. Math. Phys. 57, No. 8, 1376-1383 (2017); translation from Zh. Vychisl. Mat. Mat. Fiz. 57, No. 8, xx (2017).
MSC:  68W25 68Q17 68U05
PDFBibTeX XMLCite
Full Text: DOI

Time-space hardness of learning sparse parities. (English) Zbl 1370.68132

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). 1067-1080 (2017).
PDFBibTeX XMLCite
Full Text: DOI

Pseudopolynomial time solvability of a quadratic Euclidean problem of finding a family of disjoint subsets. (Russian, English) Zbl 1374.68499

Sib. Zh. Vychisl. Mat. 20, No. 1, 15-22 (2017); translation in Numer. Analysis Appl. 10, No. 1, 11-16 (2017).
MSC:  68T20 62H30 68Q17
PDFBibTeX XMLCite
Full Text: DOI

A fully polynomial-time approximation scheme for a special case of a balanced 2-clustering problem. (English) Zbl 1380.68401

Kochetov, Yury (ed.) et al., Discrete optimization and operations research. 9th international conference, DOOR 2016, Vladivostok, Russia, September 19–23, 2016. Proceedings. Cham: Springer (ISBN 978-3-319-44913-5/pbk; 978-3-319-44914-2/ebook). Lecture Notes in Computer Science 9869, 182-192 (2016).
MSC:  68U05 68Q17 68W25
PDFBibTeX XMLCite
Full Text: DOI

An approximation algorithm for a problem of partitioning a sequence into clusters with restrictions on their cardinalities. (English) Zbl 1380.68400

Kochetov, Yury (ed.) et al., Discrete optimization and operations research. 9th international conference, DOOR 2016, Vladivostok, Russia, September 19–23, 2016. Proceedings. Cham: Springer (ISBN 978-3-319-44913-5/pbk; 978-3-319-44914-2/ebook). Lecture Notes in Computer Science 9869, 171-181 (2016).
MSC:  68U05 68Q17 68W25
PDFBibTeX XMLCite
Full Text: DOI

Tight tradeoffs for real-time approximation of longest palindromes in streams. (English) Zbl 1380.68475

Grossi, Roberto (ed.) et al., 27th annual symposium on combinatorial pattern matching, CPM 2016, Tel Aviv, Israel, June 27–29, 2016. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-012-5). LIPIcs – Leibniz International Proceedings in Informatics 54, Article 18, 13 p. (2016).
PDFBibTeX XMLCite
Full Text: DOI arXiv

On the uncontended complexity of anonymous consensus. (English) Zbl 1380.68040

Anceaume, Emmanuelle (ed.) et al., 19th international conference on principles of distributed systems, OPODIS 2015, Rennes, France, December 14–17, 2015. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-98-9). LIPIcs – Leibniz International Proceedings in Informatics 46, Article 12, 16 p. (2016).
MSC:  68M14 68Q25
PDFBibTeX XMLCite
Full Text: DOI

Polynomial-time approximation scheme for a problem of partitioning a finite set into two clusters. (English. Russian original) Zbl 1362.68292

Proc. Steklov Inst. Math. 295, Suppl. 1, S47-S56 (2016); translation from Tr. Inst. Mat. Mekh. (Ekaterinburg) 21, No. 3, 100-109 (2015).
MSC:  68W25 62H30 68Q17
PDFBibTeX XMLCite
Full Text: DOI

On the complexity and approximability of some Euclidean optimal summing problems. (English. Russian original) Zbl 1400.68248

Comput. Math. Math. Phys. 56, No. 10, 1813-1817 (2016); translation from Zh. Vychisl. Mat. Mat. Fiz. 56, No. 10, 1831-1836 (2016).
PDFBibTeX XMLCite
Full Text: DOI

Filter Results by …

Document Type

all top 5

Author

all top 5

Serial

all top 5

Year of Publication

all top 3

Main Field

all top 3

Software