Document Open Access Logo

Fully-Dynamic Graph Sparsifiers Against an Adaptive Adversary

Authors Aaron Bernstein, Jan van den Brand, Maximilian Probst Gutenberg, Danupon Nanongkai, Thatchaphol Saranurak, Aaron Sidford, He Sun

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2022.20.pdf
  • Filesize: 0.72 MB
  • 20 pages

Document Identifiers

Author Details

Aaron Bernstein
  • Rutgers University, Piscataway, NJ, USA
Jan van den Brand
  • Simons Institute, Berkeley, CA, USA
  • University of California Berkeley, CA, USA
Maximilian Probst Gutenberg
  • ETH Zürich, Switzerland
Danupon Nanongkai
  • University of Copenhagen, Denmark
  • KTH Royal Institute of Technology, Stockholm, Sweden
Thatchaphol Saranurak
  • University of Michigan, Ann Arbor, MI, USA
Aaron Sidford
  • Stanford University, CA, USA
He Sun
  • University of Edinburgh, UK

Funding

  • Bernstein, Aaron: Funded by NSF Career grant 1942010.
  • van den Brand, Jan: Funded by ONR BRC grant N00014-18-1-2562 and by the Simons Institute for the Theory of Computing through a Simons-Berkeley Postdoctoral Fellowship. Research partially done at KTH.
  • Probst Gutenberg, Maximilian: Research partially done while at University of Copenhagen.
  • Nanongkai, Danupon: This project has received funding from the European Research Council (ERC) under the European Unions Horizon 2020 research and innovation programme under grant agreement No 715672. Also partially supported by the Swedish Research Council (Reg. No. 2015-04659 and 2019-05622).
  • Saranurak, Thatchaphol: Research partially done at KTH and supported by the Swedish Research Council (Reg. No. 2015-04659).
  • Sidford, Aaron: Supported in part by a Microsoft Research Faculty Fellowship, NSF CAREER Award CCF-1844855, NSF Grant CCF-1955039, a PayPal research award, and a Sloan Research Fellowship.
  • Sun, He: Funded by an EPSRC Early Career Fellowship (EP/T00729X/1).

Acknowledgements

We thank Julia Chuzhoy and Gramoz Goranci for discussions.

Cite AsGet BibTex

Aaron Bernstein, Jan van den Brand, Maximilian Probst Gutenberg, Danupon Nanongkai, Thatchaphol Saranurak, Aaron Sidford, and He Sun. Fully-Dynamic Graph Sparsifiers Against an Adaptive Adversary. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 20:1-20:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ICALP.2022.20

Abstract

Designing efficient dynamic graph algorithms against an adaptive adversary is a major goal in the field of dynamic graph algorithms and has witnessed many exciting recent developments in, e.g., dynamic matching (Wajc STOC'20) and decremental shortest paths (Chuzhoy and Khanna STOC'19). Compared to other graph primitives (e.g. spanning trees and matchings), designing such algorithms for graph spanners and (more broadly) graph sparsifiers poses a unique challenge since there is no fast deterministic algorithm known for static computation and the lack of a way to adjust the output slowly (known as "small recourse/replacements"). This paper presents the first non-trivial efficient adaptive algorithms for maintaining many sparsifiers against an adaptive adversary. Specifically, we present algorithms that maintain 1) a polylog(n)-spanner of size Õ(n) in polylog(n) amortized update time, 2) an O(k)-approximate cut sparsifier of size Õ(n) in Õ(n^{1/k}) amortized update time, and 3) a polylog(n)-approximate spectral sparsifier in polylog(n) amortized update time. Our bounds are the first non-trivial ones even when only the recourse is concerned. Our results hold even against a stronger adversary, who can access the random bits previously used by the algorithms and the amortized update time of all algorithms can be made worst-case by paying sub-polynomial factors. Our spanner result resolves an open question by Ahmed et al. (2019) and our results and techniques imply additional improvements over existing results, including (i) answering open questions about decremental single-source shortest paths by Chuzhoy and Khanna (STOC'19) and Gutenberg and Wulff-Nilsen (SODA'20), implying a nearly-quadratic time algorithm for approximating minimum-cost unit-capacity flow and (ii) de-amortizing a result of Abraham et al. (FOCS'16) for dynamic spectral sparsifiers. Our results are based on two novel techniques. The first technique is a generic black-box reduction that allows us to assume that the graph is initially an expander with almost uniform-degree and, more importantly, stays as an almost uniform-degree expander while undergoing only edge deletions. The second technique is called proactive resampling: here we constantly re-sample parts of the input graph so that, independent of an adversary’s computational power, a desired structure of the underlying graph can be always maintained. Despite its simplicity, the analysis of this sampling scheme is far from trivial, because the adversary can potentially create dependencies between the random choices used by the algorithm. We believe these two techniques could be useful for developing other adaptive algorithms.

Subject Classification

ACM Subject Classification
  • Theory of computation → Dynamic graph algorithms
Keywords
  • dynamic graph algorithm
  • adaptive adversary
  • spanner
  • sparsifier

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Ittai Abraham, David Durfee, Ioannis Koutis, Sebastian Krinninger, and Richard Peng. On fully dynamic graph sparsifiers. In FOCS, pages 335-344, 2016. URL: https://doi.org/10.1109/FOCS.2016.44.
  2. Abu Reyan Ahmed, Greg Bodwin, Faryad Darabi Sahneh, Keaton Hamm, Mohammad Javad Latifi Jebelli, Stephen G. Kobourov, and Richard Spence. Graph spanners: A tutorial review. CoRR, abs/1909.03152, 2019. Google Scholar
  3. Kook Jin Ahn, Sudipto Guha, and Andrew McGregor. Graph sketches: sparsification, spanners, and subgraphs. In PODS, pages 5-14, 2012. Google Scholar
  4. Kook Jin Ahn, Sudipto Guha, and Andrew McGregor. Spectral sparsification in dynamic graph streams. In APPROX-RANDOM, pages 1-10, 2013. Google Scholar
  5. Ingo Althöfer, Gautam Das, David P. Dobkin, Deborah Joseph, and José Soares. On sparse spanners of weighted graphs. Discrete & Computational Geometry, 9:81-100, 1993. URL: https://doi.org/10.1007/BF02189308.
  6. Sepehr Assadi, Krzysztof Onak, Baruch Schieber, and Shay Solomon. Fully dynamic maximal independent set with sublinear update time. In STOC, pages 815-826. ACM, 2018. Google Scholar
  7. Giorgio Ausiello, Paolo Giulio Franciosa, and Giuseppe F. Italiano. Small stretch spanners on dynamic graphs. J. Graph Algorithms Appl., 10(2):365-385, 2006. Announced at ESA'05. URL: http://jgaa.info/accepted/2006/AusielloFranciosaItaliano2006.10.2.pdf, URL: https://doi.org/10.7155/jgaa.00133.
  8. Surender Baswana. Streaming algorithm for graph spanners - single pass and constant processing time per edge. Inf. Process. Lett., 106(3):110-114, 2008. URL: https://doi.org/10.1016/j.ipl.2007.11.001.
  9. Surender Baswana, Manoj Gupta, and Sandeep Sen. Fully dynamic maximal matching in o(log n) update time (corrected version). SIAM J. Comput., 47(3):617-650, 2018. URL: https://doi.org/10.1137/16M1106158.
  10. Surender Baswana, Sumeet Khurana, and Soumojit Sarkar. Fully dynamic randomized algorithms for graph spanners. ACM Trans. Algorithms, 8(4):35:1-35:51, 2012. Announced at SODA'08. URL: https://doi.org/10.1145/2344422.2344425.
  11. Surender Baswana and Sandeep Sen. A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs. Random Struct. Algorithms, 30(4):532-563, 2007. URL: https://doi.org/10.1002/rsa.20130.
  12. Joshua D. Batson, Daniel A. Spielman, and Nikhil Srivastava. Twice-Ramanujan sparsifiers. SIAM Rev., 56(2):315-334, 2014. Google Scholar
  13. Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi, Cliff Stein, and Madhu Sudan. Fully dynamic maximal independent set with polylogarithmic update time. In FOCS, pages 382-405. IEEE Computer Society, 2019. Google Scholar
  14. Amos Beimel, Haim Kaplan, Yishay Mansour, Kobbi Nissim, Thatchaphol Saranurak, and Uri Stemmer. Dynamic algorithms against an adaptive adversary: Generic constructions and lower bounds. arXiv preprint, 2021. To appear at STOC'22. URL: http://arxiv.org/abs/2111.03980.
  15. András A Benczúr and David R Karger. Randomized approximation schemes for cuts and flows in capacitated graphs. SIAM Journal on Computing, 44(2):290-319, 2015. Google Scholar
  16. Aaron Bernstein. Deterministic partially dynamic single source shortest paths in weighted graphs. In ICALP, volume 80, pages 44:1-44:14, 2017. URL: https://doi.org/10.4230/LIPIcs.ICALP.2017.44.
  17. Aaron Bernstein and Shiri Chechik. Deterministic decremental single source shortest paths: beyond the o(mn) bound. In STOC, pages 389-397, 2016. Google Scholar
  18. Aaron Bernstein and Shiri Chechik. Deterministic partially dynamic single source shortest paths for sparse graphs. In SODA, pages 453-469, 2017. Google Scholar
  19. Aaron Bernstein and Shiri Chechik. Incremental topological sort and cycle detection in expected total time. In SODA, pages 21-34. SIAM, 2018. Google Scholar
  20. Aaron Bernstein, Sebastian Forster, and Monika Henzinger. A deamortization approach for dynamic spanner and dynamic maximal matching. In SODA, pages 1899-1918, 2019. Google Scholar
  21. Aaron Bernstein, Maximilian Probst Gutenberg, and Thatchaphol Saranurak. Deterministic decremental sssp and approximate min-cost flow in almost-linear time. arXiv preprint, 2021. URL: http://arxiv.org/abs/2101.07149.
  22. Aaron Bernstein, Maximilian Probst, and Christian Wulff-Nilsen. Decremental strongly-connected components and single-source reachability in near-linear time. In STOC, pages 365-376, 2019. Google Scholar
  23. Aaron Bernstein and Liam Roditty. Improved dynamic algorithms for maintaining approximate shortest paths under deletions. In SODA, pages 1355-1365, 2011. Google Scholar
  24. Aaron Bernstein, Jan van den Brand, Maximilian Probst Gutenberg, Danupon Nanongkai, Thatchaphol Saranurak, Aaron Sidford, and He Sun. Fully-dynamic graph sparsifiers against an adaptive adversary. CoRR, abs/2004.08432, 2020. Google Scholar
  25. Sayan Bhattacharya, Deeparnab Chakrabarty, Monika Henzinger, and Danupon Nanongkai. Dynamic algorithms for graph coloring. In SODA, pages 1-20, 2018. Google Scholar
  26. Sayan Bhattacharya, Monika Henzinger, and Giuseppe F. Italiano. Deterministic fully dynamic data structures for vertex cover and matching. In SODA, 2015. Google Scholar
  27. Sayan Bhattacharya, Monika Henzinger, and Danupon Nanongkai. New deterministic approximation algorithms for fully dynamic matching. In STOC, pages 398-411, 2016. Google Scholar
  28. Sayan Bhattacharya, Monika Henzinger, and Danupon Nanongkai. Fully dynamic approximate maximum matching and minimum vertex cover in O(log^3 n) worst case update time. In SODA, pages 470-489, 2017. Google Scholar
  29. Sayan Bhattacharya and Janardhan Kulkarni. Deterministically maintaining a (2 +ε)-approximate minimum vertex cover in o(1/ε²) amortized update time. In SODA, 2019. Google Scholar
  30. Sayan Bhattacharya, Thatchaphol Saranurak, and Pattara Sukprasert. Simple dynamic spanners with near-optimal recourse against an adaptive adversary. In submission. Google Scholar
  31. Greg Bodwin and Sebastian Krinninger. Fully dynamic spanners with worst-case update time. In ESA, pages 17:1-17:18, 2016. URL: https://doi.org/10.4230/LIPIcs.ESA.2016.17.
  32. Karl Bringmann and Konstantinos Panagiotou. Efficient sampling methods for discrete distributions. In ICALP, pages 133-144. Springer, 2012. Google Scholar
  33. Keren Censor-Hillel, Elad Haramaty, and Zohar S. Karnin. Optimal dynamic distributed MIS. In PODC, pages 217-226. ACM, 2016. Google Scholar
  34. Yi-Jun Chang and Thatchaphol Saranurak. Improved distributed expander decomposition and nearly optimal triangle enumeration. In PODC, pages 66-73, 2019. Google Scholar
  35. Shiri Chechik. Near-optimal approximate decremental all pairs shortest paths. In FOCS, 2018. Google Scholar
  36. Shiri Chechik and Tianyi Zhang. Fully dynamic maximal independent set in expected poly-log update time. In FOCS, pages 370-381. IEEE Computer Society, 2019. Google Scholar
  37. Chandra Chekuri and Kent Quanrud. Near-linear time approximation schemes for some implicit fractional packing problems. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 801-820. SIAM, 2017. Google Scholar
  38. Chandra Chekuri and Kent Quanrud. Fast approximations for metric-tsp via linear programming. arXiv preprint, 2018. URL: http://arxiv.org/abs/1802.01242.
  39. Li Chen, Gramoz Goranci, Monika Henzinger, Richard Peng, and Thatchaphol Saranurak. Fast dynamic cuts, distances and effective resistances via vertex sparsifiers. In FOCS, pages 1135-1146. IEEE, 2020. Google Scholar
  40. Timothy Chu, Yu Gao, Richard Peng, Sushant Sachdeva, Saurabh Sawlani, and Junxing Wang. Graph sparsification, spectral sketches, and faster resistance computation, via short cycle decompositions. In FOCS, pages 361-372, 2018. URL: https://doi.org/10.1109/FOCS.2018.00042.
  41. Julia Chuzhoy, Yu Gao, Jason Li, Danupon Nanongkai, Richard Peng, and Thatchaphol Saranurak. A deterministic algorithm for balanced cut with applications to dynamic connectivity, flows, and beyond. CoRR, abs/1910.08025, 2019. Google Scholar
  42. Julia Chuzhoy and Sanjeev Khanna. A new algorithm for decremental single-source shortest paths with applications to vertex-capacitated flow and cut problems. In STOC, pages 389-400, 2019. Google Scholar
  43. Julia Chuzhoy and Thatchaphol Saranurak. Deterministic algorithms for decremental shortest paths via layered core decomposition. In SODA, pages 2478-2496. SIAM, 2021. Google Scholar
  44. Bilel Derbel, Mohamed Mosbah, and Akka Zemmari. Sublinear fully distributed partition with applications. Theory Comput. Syst., 47(2):368-404, 2010. URL: https://doi.org/10.1007/s00224-009-9190-x.
  45. Luc Devroye. Nonuniform random variate generation. Handbooks in operations research and management science, 13:83-121, 2006. Google Scholar
  46. David Durfee, Yu Gao, Gramoz Goranci, and Richard Peng. Fully dynamic effective resistances. CoRR, abs/1804.04038, 2018. Google Scholar
  47. David Durfee, Yu Gao, Gramoz Goranci, and Richard Peng. Fully dynamic spectral vertex sparsifiers and applications. In STOC, pages 914-925, 2019. Google Scholar
  48. Michael Elkin. Streaming and fully dynamic centralized algorithms for constructing and maintaining sparse spanners. ACM Trans. Algorithms, 7(2):20:1-20:17, 2011. Announced at ICALP'07. URL: https://doi.org/10.1145/1921659.1921666.
  49. David Eppstein, Zvi Galil, Giuseppe F. Italiano, and Amnon Nissenzweig. Sparsification - a technique for speeding up dynamic graph algorithms. J. ACM, 44(5):669-696, 1997. Google Scholar
  50. Shimon Even and Yossi Shiloach. An on-line edge-deletion problem. Journal of the ACM (JACM), 28(1):1-4, 1981. Google Scholar
  51. Joan Feigenbaum, Sampath Kannan, Andrew McGregor, Siddharth Suri, and Jian Zhang. Graph distances in the streaming model: the value of space. In SODA, pages 745-754, 2005. URL: http://dl.acm.org/citation.cfm?id=1070432.1070537.
  52. Lisa Fleischer. Approximating fractional multicommodity flow independent of the number of commodities. SIAM J. Discrete Math., 13(4):505-520, 2000. announced at FOCS'99. URL: https://doi.org/10.1137/S0895480199355754.
  53. Wai Shing Fung, Ramesh Hariharan, Nicholas J. A. Harvey, and Debmalya Panigrahi. A general framework for graph sparsification. In STOC, pages 71-80, 2011. Google Scholar
  54. Yu Gao, Yang P Liu, and Richard Peng. Fully dynamic electrical flows: sparse maxflow faster than goldberg-rao. arXiv preprint, 2021. URL: http://arxiv.org/abs/2101.07233.
  55. Naveen Garg and Jochen Könemann. Faster and simpler algorithms for multicommodity flow and other fractional packing problems. SIAM J. Comput., 37(2):630-652, 2007. URL: https://doi.org/10.1137/S0097539704446232.
  56. Pawel Gawrychowski, Shay Mozes, and Oren Weimann. Minimum cut in o(m log² n) time. In ICALP, volume 168 of LIPIcs, pages 57:1-57:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. Google Scholar
  57. Mohsen Ghaffari and Fabian Kuhn. Derandomizing distributed algorithms with small messages: Spanners and dominating set. In DISC, pages 29:1-29:17, 2018. URL: https://doi.org/10.4230/LIPIcs.DISC.2018.29.
  58. Ofer Grossman and Merav Parter. Improved deterministic distributed construction of spanners. In DISC, pages 24:1-24:16, 2017. URL: https://doi.org/10.4230/LIPIcs.DISC.2017.24.
  59. Anupam Gupta, Ravishankar Krishnaswamy, Amit Kumar, and Sahil Singla. Online carpooling using expander decompositions. In FSTTCS, volume 182 of LIPIcs, pages 23:1-23:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. Google Scholar
  60. Maximilian Probst Gutenberg, Virginia Vassilevska Williams, and Nicole Wein. New algorithms and hardness for incremental single-source shortest paths in directed graphs. In Symposium on Theory of Computing, 2020. URL: http://arxiv.org/abs/2001.10751.
  61. Maximilian Probst Gutenberg and Christian Wulff-Nilsen. Decremental SSSP in weighted digraphs: Faster and against an adaptive adversary. In SODA, pages 2542-2561, 2020. Google Scholar
  62. Maximilian Probst Gutenberg and Christian Wulff-Nilsen. Deterministic algorithms for decremental approximate shortest paths: Faster and simpler. In SODA, pages 2522-2541, 2020. Google Scholar
  63. Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai. Decremental single-source shortest paths on undirected graphs in near-linear total update time. J. ACM, 65(6):36:1-36:40, 2018. announced at FOCS'14. Google Scholar
  64. Monika Rauch Henzinger and Valerie King. Maintaining minimum spanning trees in dynamic graphs. In ICALP, volume 1256 of Lecture Notes in Computer Science, pages 594-604. Springer, 1997. Google Scholar
  65. Jacob Holm and Eva Rotenberg. Dynamic planar embeddings of dynamic graphs. Theory Comput. Syst., 61(4):1054-1083, 2017. Google Scholar
  66. Jacob Holm and Eva Rotenberg. Fully-dynamic planarity testing in polylogarithmic time. In STOC, pages 167-180. ACM, 2020. Google Scholar
  67. Arun Jambulapati and Aaron Sidford. Efficient Õ(n/ε) spectral sketches for the laplacian and its pseudoinverse. In SODA, pages 2487-2503. SIAM, 2018. Google Scholar
  68. Bruce M. Kapron, Valerie King, and Ben Mountjoy. Dynamic graph connectivity in polylogarithmic worst case time. In SODA, pages 1131-1142, 2013. URL: https://doi.org/10.1137/1.9781611973105.81.
  69. George Karakostas. Faster approximation schemes for fractional multicommodity flow problems. ACM Trans. Algorithms, 4(1):13:1-13:17, 2008. URL: https://doi.org/10.1145/1328911.1328924.
  70. Ken-ichi Kawarabayashi and Mikkel Thorup. Deterministic global minimum cut of a simple graph in near-linear time. In STOC, pages 665-674. ACM, 2015. Google Scholar
  71. Donald Ervin Knuth. Seminumerical algorithms. The art of computer programming, 2, 1997. Google Scholar
  72. Huan Li, He Sun, and Luca Zanetti. Hermitian Laplacians and a Cheeger inequality for the Max-2-Lin problem. In ESA, pages 71:1-71:14, 2019. Google Scholar
  73. Aleksander Madry. Faster approximation schemes for fractional multicommodity flow problems via dynamic graph algorithms. In STOC, pages 121-130, 2010. URL: https://doi.org/10.1145/1806689.1806708.
  74. Morteza Monemizadeh. Dynamic maximal independent set. CoRR, abs/1906.09595, 2019. Google Scholar
  75. Sagnik Mukhopadhyay and Danupon Nanongkai. Weighted min-cut: Sequential, cut-query and streaming algorithms. In STOC, 2020. Google Scholar
  76. Danupon Nanongkai and Thatchaphol Saranurak. Dynamic spanning forest with worst-case update time: adaptive, Las vegas, and O(n^1/2-ε)-time. In STOC, pages 1122-1129, 2017. URL: https://doi.org/10.1145/3055399.3055447.
  77. Danupon Nanongkai, Thatchaphol Saranurak, and Christian Wulff-Nilsen. Dynamic minimum spanning forest with subpolynomial worst-case update time. In FOCS, pages 950-961, 2017. Google Scholar
  78. Liam Roditty, Mikkel Thorup, and Uri Zwick. Deterministic constructions of approximate distance oracles and spanners. In ICALP, pages 261-272, 2005. URL: https://doi.org/10.1007/11523468_22.
  79. Liam Roditty and Uri Zwick. On dynamic shortest paths problems. Algorithmica, 61(2):389-401, 2011. URL: https://doi.org/10.1007/s00453-010-9401-5.
  80. Thatchaphol Saranurak and Di Wang. Expander decomposition and pruning: Faster, stronger, and simpler. In SODA, pages 2616-2635, 2019. Google Scholar
  81. Jonah Sherman. Nearly maximum flows in nearly linear time. In FOCS, pages 263-269, 2013. Google Scholar
  82. Shay Solomon. Fully dynamic maximal matching in constant update time. In FOCS, pages 325-334, 2016. URL: https://doi.org/10.1109/FOCS.2016.43.
  83. Daniel A. Spielman and Shang-Hua Teng. Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems. In STOC, pages 81-90, 2004. Google Scholar
  84. Luca Trevisan. Approximation algorithms for unique games. In FOCS, pages 197-205. IEEE Computer Society, 2005. Google Scholar
  85. Jan van den Brand, Yin Tat Lee, Yang P Liu, Thatchaphol Saranurak, Aaron Sidford, Zhao Song, and Di Wang. Minimum cost flows, mdps, and l1-regression in nearly linear time for dense instances. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 859-869, 2021. Google Scholar
  86. Jan van den Brand, Yin Tat Lee, Danupon Nanongkai, Richard Peng, Thatchaphol Saranurak, Aaron Sidford, Zhao Song, and Di Wang. Bipartite matching in nearly-linear time on moderately dense graphs. In FOCS, pages 919-930. IEEE, 2020. Google Scholar
  87. David Wajc. Rounding dynamic matchings against an adaptive adversary. Symposium on Theory of Computing, 2020. URL: http://arxiv.org/abs/1911.05545.
  88. Christian Wulff-Nilsen. Fully-dynamic minimum spanning forest with improved worst-case update time. In STOC, pages 1130-1143, 2017. URL: https://doi.org/10.1145/3055399.3055415.
  89. Anastasios Zouzias. A matrix hyperbolic cosine algorithm and applications. In International Colloquium on Automata, Languages, and Programming, pages 846-858. Springer, 2012. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact