×

Found 302 Documents (Results 1–100)

100
MathJax

Network decomposition and distributed derandomization (invited paper). (English) Zbl 07581056

Richa, Andrea Werneck (ed.) et al., Structural information and communication complexity. 27th international colloquium, SIROCCO 2020, Paderborn, Germany, June 29 – July 1, 2020. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12156, 3-18 (2020).
MSC:  68Mxx 68Q11 68R10
PDF BibTeX XML Cite
Full Text: DOI

Optimal error pseudodistributions for Read-once branching programs. (English) Zbl 07561753

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 25, 27 p. (2020).
MSC:  68Q25
PDF BibTeX XML Cite
Full Text: DOI

Hitting sets give two-sided derandomization of small space. (English) Zbl 07561738

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 10, 25 p. (2020).
MSC:  68Q25
PDF BibTeX XML Cite
Full Text: DOI

Factoring polynomials over finite fields with linear Galois groups: an additive combinatorics approach. (English) Zbl 07559413

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 42, 14 p. (2020).
MSC:  68Qxx
PDF BibTeX XML Cite
Full Text: DOI

Simple, deterministic, constant-round coloring in the congested clique. (English) Zbl 07323204

Cachin, Christian (ed.) et al., Proceedings of the 39th ACM symposium on principles of distributed computing, PODC ’20, virtual event, August 3–7, 2020. New York, NY: Association for Computing Machinery (ACM). 309-318 (2020).
MSC:  68M14 68W15
PDF BibTeX XML Cite
Full Text: DOI arXiv Link

Sharp threshold results for computational complexity. (English) Zbl 07298332

Makarychev, Konstantin (ed.) et al., Proceedings of the 52nd annual ACM SIGACT symposium on theory of computing, STOC ’20, Chicago, IL, USA, June 22–26, 2020. New York, NY: Association for Computing Machinery (ACM). 1335-1348 (2020).
MSC:  68Qxx
PDF BibTeX XML Cite
Full Text: DOI

Strong average-case lower bounds from non-trivial derandomization. (English) Zbl 07298331

Makarychev, Konstantin (ed.) et al., Proceedings of the 52nd annual ACM SIGACT symposium on theory of computing, STOC ’20, Chicago, IL, USA, June 22–26, 2020. New York, NY: Association for Computing Machinery (ACM). 1327-1334 (2020).
MSC:  68Qxx
PDF BibTeX XML Cite
Full Text: DOI

Polylogarithmic-time deterministic network decomposition and distributed derandomization. (English) Zbl 07298253

Makarychev, Konstantin (ed.) et al., Proceedings of the 52nd annual ACM SIGACT symposium on theory of computing, STOC ’20, Chicago, IL, USA, June 22–26, 2020. New York, NY: Association for Computing Machinery (ACM). 350-363 (2020).
MSC:  68Qxx
PDF BibTeX XML Cite
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
PDF BibTeX XML Cite
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
PDF BibTeX XML Cite
Full Text: DOI

Equality alone does not simulate randomness. (English) Zbl 07564414

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 14, 11 p. (2019).
MSC:  68Q25
PDF BibTeX XML Cite
Full Text: DOI

Typically-correct derandomization for small time and space. (English) Zbl 07564409

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 9, 39 p. (2019).
MSC:  68Q25
PDF BibTeX XML Cite
Full Text: DOI

Deterministic combinatorial replacement paths and distance sensitivity oracles. (English) Zbl 07561505

Baier, Christel (ed.) et al., 46th international colloquium on automata, languages, and programming, ICALP 2019, Patras, Greece, July 9–12, 2019. Proceedings. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 132, Article 12, 14 p. (2019).
MSC:  68Nxx 68Qxx
PDF BibTeX XML Cite
Full Text: DOI

Pseudorandom generators from the second Fourier level and applications to AC0 with parity gates. (English) Zbl 07559065

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 22, 15 p. (2019).
MSC:  68Qxx
PDF BibTeX XML Cite
Full Text: DOI

Deterministic reduction of integer nonsingular linear system solving to matrix multiplication. (English) Zbl 1467.65042

Bradford, Russell (ed.), Proceedings of the 44th international symposium on symbolic and algebraic computation, ISSAC ’19, Beijing, China, July 15–18, 2019. New York, NY: Association for Computing Machinery (ACM). 58-65 (2019).
MSC:  65F99 15A06
PDF BibTeX XML Cite
Full Text: DOI

Subspace arrangements, graph rigidity and derandomization through submodular optimization. (English) Zbl 1452.68089

Bárány, Imre (ed.) et al., Building bridges II. Mathematics of László Lovász. Conference in celebration of László Lovász’ 70th birthday, Budapest, Hungary, July 2–6, 2018. Berlin: Springer. Bolyai Soc. Math. Stud. 28, 377-415 (2019).
PDF BibTeX XML Cite
Full Text: DOI arXiv

Fooling polytopes. (English) Zbl 1433.68605

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). 614-625 (2019).
PDF BibTeX XML Cite
Full Text: DOI arXiv

Bootstrapping results for threshold circuits “just beyond” known lower bounds. (English) Zbl 1433.68137

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). 34-41 (2019).
MSC:  68Q06 68Q17
PDF BibTeX XML Cite
Full Text: DOI

Towards a general direct product testing theorem. (English) Zbl 07561316

Ganguly, Sumit (ed.) et al., 38th IARCS annual conference on foundations of software technology and theoretical computer science, FSTTCS 2018, Ahmedabad, India, December 11–13, 2018. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 122, Article 11, 17 p. (2018).
MSC:  68N30 68Qxx
PDF BibTeX XML Cite
Full Text: DOI

Adapting local sequential algorithms to the distributed setting. (English) Zbl 07561287

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 35, 17 p. (2018).
MSC:  68M14 68W15
PDF BibTeX XML Cite
Full Text: DOI

Derandomizing distributed algorithms with small messages: spanners and dominating set. (English) Zbl 07561281

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 29, 17 p. (2018).
MSC:  68M14 68W15
PDF BibTeX XML Cite
Full Text: DOI

Pseudo-derandomizing learning and approximation. (English) Zbl 07378667

Blais, Eric (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 21st international workshop, APPROX 2018, and 22nd international workshop, RANDOM 2018 August 20–22, 2018, Princeton, USA. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 116, Article 55, 19 p. (2018).
MSC:  68W20 68W25 90C27
PDF BibTeX XML Cite
Full Text: DOI

Satisfiability and derandomization for small polynomial threshold circuits. (English) Zbl 07378658

Blais, Eric (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 21st international workshop, APPROX 2018, and 22nd international workshop, RANDOM 2018 August 20–22, 2018, Princeton, USA. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 116, Article 46, 19 p. (2018).
MSC:  68W20 68W25 90C27
PDF BibTeX XML Cite
Full Text: DOI

Deterministically counting satisfying assignments for constant-depth circuits with parity gates, with implications for lower bounds. (English) Zbl 07378395

Potapov, Igor (ed.) et al., 43rd international symposium on mathematical foundations of computer science. MFCS 2018, Liverpool, United Kingdom, August 27–31, 2018. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 117, Article 78, 15 p. (2018).
MSC:  68Qxx
PDF BibTeX XML Cite
Full Text: DOI

Chain, generalization of covering code, and deterministic algorithm for \(k\)-SAT. (English) Zbl 07376015

Chatzigiannakis, Ioannis (ed.) et al., 45th international colloquium on automata, languages, and programming. ICALP 2018, Prague, Czech Republic, July 9–13, 2018. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 107, Article 88, 13 p. (2018).
MSC:  68Nxx 68Qxx
PDF BibTeX XML Cite
Full Text: DOI arXiv

Isolating a vertex via lattices: polytopes with totally unimodular faces. (English) Zbl 07376001

Chatzigiannakis, Ioannis (ed.) et al., 45th international colloquium on automata, languages, and programming. ICALP 2018, Prague, Czech Republic, July 9–13, 2018. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 107, Article 74, 14 p. (2018).
MSC:  68Nxx 68Qxx
PDF BibTeX XML Cite
Full Text: DOI

Towards blackbox identity testing of log-variate circuits. (English) Zbl 07375981

Chatzigiannakis, Ioannis (ed.) et al., 45th international colloquium on automata, languages, and programming. ICALP 2018, Prague, Czech Republic, July 9–13, 2018. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 107, Article 54, 16 p. (2018).
MSC:  68Nxx 68Qxx
PDF BibTeX XML Cite
Full Text: DOI

Fine-grained derandomization: from problem-centric to resource-centric complexity. (English) Zbl 07375954

Chatzigiannakis, Ioannis (ed.) et al., 45th international colloquium on automata, languages, and programming. ICALP 2018, Prague, Czech Republic, July 9–13, 2018. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 107, Article 27, 16 p. (2018).
MSC:  68Nxx 68Qxx
PDF BibTeX XML Cite
Full Text: DOI

Lower bounds on black-box reductions of hitting to density estimation. (English) Zbl 1487.68262

Niedermeier, Rolf (ed.) et al., 35th symposium on theoretical aspects of computer science, STACS 2018, Caen, France, February 28 – March 3, 2018. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 96, Article 58, 13 p. (2018).
PDF BibTeX XML Cite
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).
PDF BibTeX XML Cite
Full Text: DOI

Bootstrapping variables in algebraic circuits. (English) Zbl 1427.68356

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). 1166-1179 (2018).
PDF BibTeX XML Cite
Full Text: DOI

A matrix expander Chernoff bound. (English) Zbl 1442.60007

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). 1102-1114 (2018).
MSC:  60B20 60G50
PDF BibTeX XML Cite
Full Text: DOI arXiv

Quantified derandomization of linear threshold circuits. (English) Zbl 1428.68169

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). 855-865 (2018).
PDF BibTeX XML Cite
Full Text: DOI arXiv

Hitting sets with near-optimal error for read-once branching programs. (English) Zbl 1427.68095

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). 353-362 (2018).
MSC:  68Q15 68W20
PDF BibTeX XML Cite
Full Text: DOI

On some computations on sparse polynomials. (English) Zbl 1470.68043

Jansen, Klaus (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 20th international workshop, APPROX 2017 and 21st international workshop, RANDOM 2017, Berkeley, CA, USA, August 16–18, 2017. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 81, Article 48, 21 p. (2017).
MSC:  68Q06 68W20
PDF BibTeX XML Cite
Full Text: DOI

Complete derandomization of identity testing and reconstruction of read-once formulas. (English) Zbl 1440.68329

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 32, 13 p. (2017).
MSC:  68W20 68Q06 68W40
PDF BibTeX XML Cite
Full Text: DOI

Improved bounds for quantified derandomization of constant-depth circuits and polynomials. (English) Zbl 1440.68131

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 13, 48 p. (2017).
PDF BibTeX XML Cite
Full Text: DOI

Derandomizing isolation in space-bounded settings. (English) Zbl 1440.68076

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 5, 32 p. (2017).
PDF BibTeX XML Cite
Full Text: DOI

The journey from NP to TFNP hardness. (English) Zbl 1402.68067

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 60, 21 p. (2017).
MSC:  68Q15 68Q17 68Q25
PDF BibTeX XML Cite
Full Text: DOI

On algorithmic statistics for space-bounded algorithms. (English) Zbl 1435.68128

Weil, Pascal (ed.), Computer science – theory and applications. 12th international computer science symposium in Russia, CSR 2017, Kazan, Russia, June 8–12, 2017. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 10304, 232-244 (2017).
MSC:  68Q30 62A01 68W20
PDF BibTeX XML Cite
Full Text: DOI arXiv

Linear matroid intersection is in quasi-NC. (English) Zbl 1370.68325

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). 821-830 (2017).
MSC:  68W20 05B35 90C27
PDF BibTeX XML Cite
Full Text: DOI

Pseudodeterministic constructions in subexponential time. (English) Zbl 1370.68326

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). 665-677 (2017).
MSC:  68W20 11A41 68Q25
PDF BibTeX XML Cite
Full Text: DOI arXiv Link

Targeted pseudorandom generators, simulation advice generators, and derandomizing logspace. (English) Zbl 1370.68107

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). 629-640 (2017).
MSC:  68Q15 68W20
PDF BibTeX XML Cite
Full Text: DOI arXiv

A no-go theorem for derandomized parallel repetition: beyond Feige-Kilian. (English) Zbl 1398.68185

Jansen, Klaus (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. Proceedings of the 19th international workshop on approximation algorithms for combinatorial optimization problems, APPROX 2016, and the 20th international workshop on randomization and computation, RANDOM 2016, Paris, France, September 7–9, 2016. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-018-7). LIPIcs – Leibniz International Proceedings in Informatics 60, Article 42, 29 p. (2016).
MSC:  68Q15 68Q10 68Q17
PDF BibTeX XML Cite
Full Text: DOI arXiv

Explicit correlation amplifiers for finding outlier correlations in deterministic subquadratic time. (English) Zbl 1397.68218

Sankowski, Piotr (ed.) et al., 24th annual European symposium on algorithms, ESA 2016, Aarhus, Denmark, August 22–24, 2016. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-015-6). LIPIcs – Leibniz International Proceedings in Informatics 57, Article 52, 17 p. (2016).
PDF BibTeX XML Cite
Full Text: DOI arXiv

Derandomizing isolation lemma for \(K_{3,3}\)-free and \(K_5\)-free bipartite graphs. (English) Zbl 1388.68208

Ollinger, Nicolas (ed.) et al., 33rd symposium on theoretical aspects of computer science, STACS 2016, Orléans, France, February 17–20, 2016. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-001-9). LIPIcs – Leibniz International Proceedings in Informatics 47, Article 10, 15 p. (2016).
PDF BibTeX XML Cite
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
PDF BibTeX XML Cite
Full Text: DOI arXiv

Pseudorandomness when the odds are against you. (English) Zbl 1380.68434

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 9, 35 p. (2016).
MSC:  68W20 68Q17 68Q25
PDF BibTeX XML Cite
Full Text: DOI

New extractors for interleaved sources. (English) Zbl 1380.68183

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 7, 28 p. (2016).
PDF BibTeX XML Cite
Full Text: DOI

Bipartite perfect matching is in quasi-NC. (English) Zbl 1373.68267

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). 754-763 (2016).
PDF BibTeX XML Cite
Full Text: DOI arXiv Link

A deterministic almost-tight distributed algorithm for approximating single-source shortest paths. (English) Zbl 1375.68218

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). 489-498 (2016).
PDF BibTeX XML Cite
Full Text: DOI arXiv

Low-rank approximation of a matrix: novel insights, new progress, and extensions. (English) Zbl 1477.65070

Kulikov, Alexander S. (ed.) et al., Computer science – theory and applications. 11th international computer science symposium in Russia, CSR 2016, St. Petersburg, Russia, June 9–13, 2016. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 9691, 352-366 (2016).
MSC:  65F55
PDF BibTeX XML Cite
Full Text: DOI arXiv

Filter Results by …

Document Type

Reviewing State

all top 5

Author

all top 5

Year of Publication

all top 3

Classification