8 Search Results for "Martin, Christopher"

Document
DOI: 10.4230/LIPIcs.ITCS.2024.62
On the Complexity of Algorithms with Predictions for Dynamic Graph Problems

Authors: Monika Henzinger, Barna Saha, Martin P. Seybold, and Christopher Ye

Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)

Abstract
Algorithms with predictions is a new research direction that leverages machine learned predictions for algorithm design. So far a plethora of recent works have incorporated predictions to improve on worst-case bounds for online problems. In this paper, we initiate the study of complexity of dynamic data structures with predictions, including dynamic graph algorithms. Unlike online algorithms, the goal in dynamic data structures is to maintain the solution efficiently with every update. We investigate three natural models of prediction: (1) δ-accurate predictions where each predicted request matches the true request with probability δ, (2) list-accurate predictions where a true request comes from a list of possible requests, and (3) bounded delay predictions where the true requests are a permutation of the predicted requests. We give general reductions among the prediction models, showing that bounded delay is the strongest prediction model, followed by list-accurate, and δ-accurate. Further, we identify two broad problem classes based on lower bounds due to the Online Matrix Vector (OMv) conjecture. Specifically, we show that locally correctable dynamic problems have strong conditional lower bounds for list-accurate predictions that are equivalent to the non-prediction setting, unless list-accurate predictions are perfect. Moreover, we show that locally reducible dynamic problems have time complexity that degrades gracefully with the quality of bounded delay predictions. We categorize problems with known OMv lower bounds accordingly and give several upper bounds in the delay model that show that our lower bounds are almost tight. We note that concurrent work by v.d.Brand et al. [SODA '24] and Liu and Srinivas [arXiv:2307.08890] independently study dynamic graph algorithms with predictions, but their work is mostly focused on showing upper bounds.
Cite as

Monika Henzinger, Barna Saha, Martin P. Seybold, and Christopher Ye. On the Complexity of Algorithms with Predictions for Dynamic Graph Problems. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 62:1-62:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{henzinger_et_al:LIPIcs.ITCS.2024.62,
  author =	{Henzinger, Monika and Saha, Barna and Seybold, Martin P. and Ye, Christopher},
  title =	{{On the Complexity of Algorithms with Predictions for Dynamic Graph Problems}},
  booktitle =	{15th Innovations in Theoretical Computer Science Conference (ITCS 2024)},
  pages =	{62:1--62:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-309-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{287},
  editor =	{Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.62},
  URN =		{urn:nbn:de:0030-drops-195907},
  doi =		{10.4230/LIPIcs.ITCS.2024.62},
  annote =	{Keywords: Dynamic Graph Algorithms, Algorithms with Predictions}
}
Document
DOI: 10.4230/LIPIcs.ESA.2023.103
Efficient Block Approximate Matrix Multiplication

Authors: Chuhan Yang and Christopher Musco

Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)

Abstract
Randomized matrix algorithms have had significant recent impact on numerical linear algebra. One especially powerful class of methods are algorithms for approximate matrix multiplication based on sampling. Such methods typically sample individual matrix rows and columns using carefully chosen importance sampling probabilities. However, due to practical considerations like memory locality and the preservation of matrix structure, it is often preferable to sample contiguous blocks of rows and columns all together. Recently, (Wu, 2018) addressed this setting by developing an approximate matrix multiplication method based on block sampling. However, the method is inefficient, as it requires knowledge of optimal importance sampling probabilities that are expensive to compute. We address this issue by showing that the method of Wu can be accelerated through the use of a randomized implicit trace estimation method. Doing so allows us to provably reduce the cost of sampling to near-linear in the size of the matrices being multiplied, without impacting the accuracy of the final approximate matrix multiplication. Overall, this yields a fast practical algorithm, which we test on a number of synthetic and real-world data sets. We complement our algorithmic contribution with the first extensive empirical comparison of block algorithms for randomized matrix multiplication. Our method offers a significant runtime advantage over the method of (Wu, 2018) and also outperforms basic uniform sampling of blocks. However, we find another recent method of (Charalambides, 2021) which uses sub-optimal but efficiently computable sampling probabilities often (but not always) offers the best trade-off between speed and accuracy.
Cite as

Chuhan Yang and Christopher Musco. Efficient Block Approximate Matrix Multiplication. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 103:1-103:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{yang_et_al:LIPIcs.ESA.2023.103,
  author =	{Yang, Chuhan and Musco, Christopher},
  title =	{{Efficient Block Approximate Matrix Multiplication}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{103:1--103:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-295-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{274},
  editor =	{G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.103},
  URN =		{urn:nbn:de:0030-drops-187562},
  doi =		{10.4230/LIPIcs.ESA.2023.103},
  annote =	{Keywords: Approximate matrix multiplication, randomized numerical linear algebra, trace estimation}
}
Document
DOI: 10.4230/LIPIcs.ICDT.2023.16
Work-Efficient Query Evaluation with PRAMs

Authors: Jens Keppeler, Thomas Schwentick, and Christopher Spinrath

Published in: LIPIcs, Volume 255, 26th International Conference on Database Theory (ICDT 2023)

Abstract
The paper studies query evaluation in parallel constant time in the PRAM model. While it is well-known that all relational algebra queries can be evaluated in constant time on an appropriate CRCW-PRAM, this paper is interested in the efficiency of evaluation algorithms, that is, in the number of processors or, asymptotically equivalent, in the work. Naive evaluation in the parallel setting results in huge (polynomial) bounds on the work of such algorithms and in presentations of the result sets that can be extremely scattered in memory. The paper first discusses some obstacles for constant time PRAM query evaluation. It presents algorithms for relational operators that are considerably more efficient than the naive approaches. Further it explores three settings, in which efficient sequential query evaluation algorithms exist: acyclic queries, semi-join algebra queries, and join queries - the latter in the worst-case optimal framework. Under natural assumptions on the representation of the database, the work of the given algorithms matches the best sequential algorithms in the case of semi-join queries, and it comes close in the other two settings. An important tool is the compaction technique from Hagerup (1992).
Cite as

Jens Keppeler, Thomas Schwentick, and Christopher Spinrath. Work-Efficient Query Evaluation with PRAMs. In 26th International Conference on Database Theory (ICDT 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 255, pp. 16:1-16:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{keppeler_et_al:LIPIcs.ICDT.2023.16,
  author =	{Keppeler, Jens and Schwentick, Thomas and Spinrath, Christopher},
  title =	{{Work-Efficient Query Evaluation with PRAMs}},
  booktitle =	{26th International Conference on Database Theory (ICDT 2023)},
  pages =	{16:1--16:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-270-9},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{255},
  editor =	{Geerts, Floris and Vandevoort, Brecht},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2023.16},
  URN =		{urn:nbn:de:0030-drops-177589},
  doi =		{10.4230/LIPIcs.ICDT.2023.16},
  annote =	{Keywords: PRAM, query evaluation, work-efficient, parallel, acyclic queries, free-connex queries}
}
Document
DOI: 10.4230/DagRep.12.3.141
Graph Embeddings: Theory meets Practice (Dagstuhl Seminar 22132)

Authors: Martin Grohe, Stephan Günnemann, Stefanie Jegelka, and Christopher Morris

Published in: Dagstuhl Reports, Volume 12, Issue 3 (2022)

Abstract
Vectorial representations of graphs and relational structures, so-called graph embeddings, make it possible to apply standard tools from data mining, machine learning, and statistics to the graph domain. In particular, graph embeddings aim to capture important information about, both, the graph structure and available side information as a vector, to enable downstream tasks such as classification, regression, or clustering. Starting from the 1960s in chemoinformatics, research in various communities has resulted in a plethora of approaches, often with recurring ideas. However, most of the field advancements are driven by intuition and empiricism, often tailored to a specific application domain. Until recently, the area has received little stimulus from theoretical computer science, graph theory, and learning theory. The Dagstuhl Seminar 22132 "Graph Embeddings: Theory meets Practice", was aimed to gather leading applied and theoretical researchers in graph embeddings and adjacent areas, such as graph isomorphism, bio- and chemoinformatics, and graph theory, to stimulate an increased exchange of ideas between these communities.
Cite as

Martin Grohe, Stephan Günnemann, Stefanie Jegelka, and Christopher Morris. Graph Embeddings: Theory meets Practice (Dagstuhl Seminar 22132). In Dagstuhl Reports, Volume 12, Issue 3, pp. 141-155, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@Article{grohe_et_al:DagRep.12.3.141,
  author =	{Grohe, Martin and G\"{u}nnemann, Stephan and Jegelka, Stefanie and Morris, Christopher},
  title =	{{Graph Embeddings: Theory meets Practice (Dagstuhl Seminar 22132)}},
  pages =	{141--155},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2022},
  volume =	{12},
  number =	{3},
  editor =	{Grohe, Martin and G\"{u}nnemann, Stephan and Jegelka, Stefanie and Morris, Christopher},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.12.3.141},
  URN =		{urn:nbn:de:0030-drops-172727},
  doi =		{10.4230/DagRep.12.3.141},
  annote =	{Keywords: Machine Learning For Graphs, GNNs, Graph Embedding}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2017.5
Scheduling Problems over Network of Machines

Authors: Zachary Friggstad, Arnoosh Golestanian, Kamyar Khodamoradi, Christopher Martin, Mirmahdi Rahgoshay, Mohsen Rezapour, Mohammad R. Salavatipour, and Yifeng Zhang

Published in: LIPIcs, Volume 81, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)

Abstract
We consider scheduling problems in which jobs need to be processed through a (shared) network of machines. The network is given in the form of a graph the edges of which represent the machines. We are also given a set of jobs, each specified by its processing time and a path in the graph. Every job needs to be processed in the order of edges specified by its path. We assume that jobs can wait between machines and preemption is not allowed; that is, once a job is started being processed on a machine, it must be completed without interruption. Every machine can only process one job at a time. The makespan of a schedule is the earliest time by which all the jobs have finished processing. The flow time (a.k.a. the completion time) of a job in a schedule is the difference in time between when it finishes processing on its last machine and when the it begins processing on its first machine. The total flow time (or the sum of completion times) is the sum of flow times (or completion times) of all jobs. Our focus is on finding schedules with the minimum sum of completion times or minimum makespan. In this paper, we develop several algorithms (both approximate and exact) for the problem both on general graphs and when the underlying graph of machines is a tree. Even in the very special case when the underlying network is a simple star, the problem is very interesting as it models a biprocessor scheduling with applications to data migration.
Cite as

Zachary Friggstad, Arnoosh Golestanian, Kamyar Khodamoradi, Christopher Martin, Mirmahdi Rahgoshay, Mohsen Rezapour, Mohammad R. Salavatipour, and Yifeng Zhang. Scheduling Problems over Network of Machines. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 81, pp. 5:1-5:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{friggstad_et_al:LIPIcs.APPROX-RANDOM.2017.5,
  author =	{Friggstad, Zachary and Golestanian, Arnoosh and Khodamoradi, Kamyar and Martin, Christopher and Rahgoshay, Mirmahdi and Rezapour, Mohsen and Salavatipour, Mohammad R. and Zhang, Yifeng},
  title =	{{Scheduling Problems over Network of Machines}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)},
  pages =	{5:1--5:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-044-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{81},
  editor =	{Jansen, Klaus and Rolim, Jos\'{e} D. P. and Williamson, David P. and Vempala, Santosh S.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2017.5},
  URN =		{urn:nbn:de:0030-drops-75547},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2017.5},
  annote =	{Keywords: approximation algorithms, job-shop scheduling, min-sum edge coloring, minimum latency}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2016.56
Approximation Algorithms for Capacitated k-Travelling Repairmen Problems

Authors: Christopher S. Martin and Mohammad R. Salavatipour

Published in: LIPIcs, Volume 64, 27th International Symposium on Algorithms and Computation (ISAAC 2016)

Abstract
We study variants of the capacitated vehicle routing problem. In the multiple depot capacitated k-travelling repairmen problem (MD-CkTRP), we have a collection of clients to be served by one vehicle in a fleet of k identical vehicles based at given depots. Each client has a given demand that must be satisfied, and each vehicle can carry a total of at most Q demand before it must resupply at its original depot. We wish to route the vehicles in a way that obeys the constraints while minimizing the average time (latency) required to serve a client. This generalizes the Multi-depot k-Travelling Repairman Problem (MD-kTRP) [Chekuri and Kumar, IEEE-FOCS, 2003; Post and Swamy, ACM-SIAM SODA, 2015] to the capacitated vehicle setting, and while it has been previously studied [Lysgaard and Wohlk, EJOR, 2014; Rivera et al, Comput Optim Appl, 2015], no approximation algorithm with a proven ratio is known. We give a 42.49-approximation to this general problem, and refine this constant to 25.49 when clients have unit demands. As far as we are aware, these are the first constant-factor approximations for capacitated vehicle routing problems with a latency objective. We achieve these results by developing a framework allowing us to solve a wider range of latency problems, and crafting various orienteering-style oracles for use in this framework. We also show a simple LP rounding algorithm has a better approximation ratio for the maximum coverage problem with groups (MCG), first studied by Chekuri and Kumar [APPROX, 2004], and use it as a subroutine in our framework. Our approximation ratio for MD-CkTRP when restricted to uncapacitated setting matches the best known bound for it [Post and Swamy, ACM-SIAM SODA, 2015]. With our framework, any improvements to our oracles or our MCG approximation will result in improved approximations to the corresponding k-TRP problem.
Cite as

Christopher S. Martin and Mohammad R. Salavatipour. Approximation Algorithms for Capacitated k-Travelling Repairmen Problems. In 27th International Symposium on Algorithms and Computation (ISAAC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 64, pp. 56:1-56:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{martin_et_al:LIPIcs.ISAAC.2016.56,
  author =	{Martin, Christopher S. and Salavatipour, Mohammad R.},
  title =	{{Approximation Algorithms for Capacitated k-Travelling Repairmen Problems}},
  booktitle =	{27th International Symposium on Algorithms and Computation (ISAAC 2016)},
  pages =	{56:1--56:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-026-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{64},
  editor =	{Hong, Seok-Hee},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2016.56},
  URN =		{urn:nbn:de:0030-drops-68262},
  doi =		{10.4230/LIPIcs.ISAAC.2016.56},
  annote =	{Keywords: approximation, capacitated, latency, group coverage}
}
Document
DOI: 10.4230/LIPIcs.RTA.2010.33
Closing the Gap Between Runtime Complexity and Polytime Computability

Authors: Martin Avanzini and Georg Moser

Published in: LIPIcs, Volume 6, Proceedings of the 21st International Conference on Rewriting Techniques and Applications (2010)

Abstract
In earlier work, we have shown that for confluent TRSs, innermost polynomial runtime complexity induces polytime computability of the functions defined. In this paper, we generalise this result to full rewriting, for that we exploit graph rewriting. We give a new proof of the adequacy of graph rewriting for full rewriting that allows for a precise control of the resources copied. In sum we completely describe an implementation of rewriting on a Turing machine (TM for short). We show that the runtime complexity of the TRS and the runtime complexity of the TM is polynomially related. Our result strengthens the evidence that the complexity of a rewrite system is truthfully represented through the length of derivations. Moreover our result allows the classification of nondeterministic polytime-computation based on runtime complexity analysis of rewrite systems.
Cite as

Martin Avanzini and Georg Moser. Closing the Gap Between Runtime Complexity and Polytime Computability. In Proceedings of the 21st International Conference on Rewriting Techniques and Applications. Leibniz International Proceedings in Informatics (LIPIcs), Volume 6, pp. 33-48, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{avanzini_et_al:LIPIcs.RTA.2010.33,
  author =	{Avanzini, Martin and Moser, Georg},
  title =	{{Closing the Gap Between Runtime Complexity and Polytime Computability}},
  booktitle =	{Proceedings of the 21st International Conference on Rewriting Techniques and Applications},
  pages =	{33--48},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-18-7},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{6},
  editor =	{Lynch, Christopher},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.RTA.2010.33},
  URN =		{urn:nbn:de:0030-drops-26436},
  doi =		{10.4230/LIPIcs.RTA.2010.33},
  annote =	{Keywords: Term rewriting, graph rewriting, complexity analysis, polytime computability}
}
Document
DOI: 10.4230/LIPIcs.RTA.2010.385
Modular Complexity Analysis via Relative Complexity

Authors: Harald Zankl and Martin Korp

Published in: LIPIcs, Volume 6, Proceedings of the 21st International Conference on Rewriting Techniques and Applications (2010)

Abstract
In this paper we introduce a modular framework which allows to infer (feasible) upper bounds on the (derivational) complexity of term rewrite systems by combining different criteria. All current investigations to analyze the derivational complexity are based on a single termination proof, possibly preceded by transformations. We prove that the modular framework is strictly more powerful than the conventional setting. Furthermore, the results have been implemented and experiments show significant gains in power.
Cite as

Harald Zankl and Martin Korp. Modular Complexity Analysis via Relative Complexity. In Proceedings of the 21st International Conference on Rewriting Techniques and Applications. Leibniz International Proceedings in Informatics (LIPIcs), Volume 6, pp. 385-400, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{zankl_et_al:LIPIcs.RTA.2010.385,
  author =	{Zankl, Harald and Korp, Martin},
  title =	{{Modular Complexity Analysis via Relative Complexity}},
  booktitle =	{Proceedings of the 21st International Conference on Rewriting Techniques and Applications},
  pages =	{385--400},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-18-7},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{6},
  editor =	{Lynch, Christopher},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.RTA.2010.385},
  URN =		{urn:nbn:de:0030-drops-26659},
  doi =		{10.4230/LIPIcs.RTA.2010.385},
  annote =	{Keywords: Term rewriting, complexity analysis, relative complexity, derivation length}
}
  • Refine by Author
  • 2 Salavatipour, Mohammad R.
  • 1 Avanzini, Martin
  • 1 Friggstad, Zachary
  • 1 Golestanian, Arnoosh
  • 1 Grohe, Martin
  • Show More...

  • Refine by Classification
  • 1 Computing methodologies → Machine learning
  • 1 Mathematics of computing → Discrete mathematics
  • 1 Theory of computation → Database query processing and optimization (theory)
  • 1 Theory of computation → Dynamic graph algorithms
  • 1 Theory of computation → Shared memory algorithms
  • Show More...

  • Refine by Keyword
  • 2 Term rewriting
  • 2 complexity analysis
  • 1 Algorithms with Predictions
  • 1 Approximate matrix multiplication
  • 1 Dynamic Graph Algorithms
  • Show More...

  • Refine by Type
  • 8 document

  • Refine by Publication Year
  • 2 2010
  • 2 2023
  • 1 2016
  • 1 2017
  • 1 2022
  • Show More...

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