2021

• 
  Aziz, Haris; Cseh, Agnes; Dickerson, John; McElfresh, DuncanOptimal Kidney Exchange with Immunosuppressants. Conference on Artificial Intelligence (AAAI) 2021
  [ BibTeX ]
   
  @inproceedings{haris2021optimal, author = {Aziz, Haris and Cseh, Agnes and Dickerson, John and McElfresh, Duncan}, booktitle = {Conference on Artificial Intelligence (AAAI)}, keywords = {aaai agnescseh duncanmcelfresh harisaziz johndickerson year2021}, title = {Optimal Kidney Exchange with Immunosuppressants}, year = 2021 }
• 
  Bilò, Davide; Friedrich, Tobias; Lenzner, Pascal; Lowski, Stefanie; Melnichenko, AnnaSelfish Creation of Social Networks. Conference on Artificial Intelligence (AAAI) 2021
  [ BibTeX ]
   
  @inproceedings{bilo2021selfish, author = {Bilò, Davide and Friedrich, Tobias and Lenzner, Pascal and Lowski, Stefanie and Melnichenko, Anna}, booktitle = {Conference on Artificial Intelligence (AAAI)}, keywords = {aaai annamelnichenko davidebilo pascallenzner stefanielowski tobiasfriedrich year2021}, title = {Selfish Creation of Social Networks}, year = 2021 }
• 
  Kraiczy, Sonja; Cseh, Ágnes; Manlove, DavidOn weakly and strongly popular rankings. International Conference on Autonomous Agents and Multiagent Systems (AAMAS) 2021
  [ BibTeX ]
   
  @inproceedings{kraiczy2021weakly, author = {Kraiczy, Sonja and Cseh, Ágnes and Manlove, David}, booktitle = {International Conference on Autonomous Agents and Multiagent Systems (AAMAS)}, keywords = {aamas agnescseh davidfmanlove sonjakraiczy year2021}, title = {On weakly and strongly popular rankings}, year = 2021 }
• 
  Aziz, Haris; Chan, Hau; Cseh, Ágnes; Li, Bo; Ramezani, Fahimeh; Wang, ChenhaoMulti-Robot Task Allocation—Complexity and Approximation. International Conference on Autonomous Agents and Multiagent Systems (AAMAS) 2021
  [ BibTeX ]
   
  @inproceedings{aziz2021multirobot, author = {Aziz, Haris and Chan, Hau and Cseh, Ágnes and Li, Bo and Ramezani, Fahimeh and Wang, Chenhao}, booktitle = {International Conference on Autonomous Agents and Multiagent Systems (AAMAS)}, keywords = {aamas agnescseh boli chenhaowang fahimehramezani harisaziz hauchan year2021}, title = {Multi-Robot Task Allocation—Complexity and Approximation}, year = 2021 }
• 
  Casel, Katrin; Schmid, Markus L.Fine-Grained Complexity of Regular Path Queries. International Conference on Database Theory (ICDT) 2021
  [ Abstract ] [ BibTeX ]
   
  A regular path query (RPQ) is a regular expression \(q\) that returns all node pairs \((u, v)\) from a graph database that are connected by an arbitrary path labelled with a word from \(L(q)\). The obvious algorithmic approach to RPQ-evaluation (called PG-approach), i.e., constructing the product graph between an NFA for \(q\) and the graph database, is appealing due to its simplicity and also leads to efficient algorithms. However, it is unclear whether the PG-approach is optimal. We address this question by thoroughly investigating which upper complexity bounds can be achieved by the PG-approach, and we complement these with conditional lower bounds (in the sense of the fine-grained complexity framework). A special focus is put on enumeration and delay bounds, as well as the data complexity perspective. A main insight is that we can achieve optimal (or near optimal) algorithms with the PG-approach, but the delay for enumeration is rather high (linear in the database). We explore three successful approaches towards enumeration with sub-linear delay: super-linear preprocessing, approximations of the solution sets, and restricted classes of RPQs.
  @inproceedings{casel2021finegrained, abstract = {A regular path query (RPQ) is a regular expression \(q\) that returns all node pairs \((u, v)\) from a graph database that are connected by an arbitrary path labelled with a word from \(L(q)\). The obvious algorithmic approach to RPQ-evaluation (called PG-approach), i.e., constructing the product graph between an NFA for \(q\) and the graph database, is appealing due to its simplicity and also leads to efficient algorithms. However, it is unclear whether the PG-approach is optimal. We address this question by thoroughly investigating which upper complexity bounds can be achieved by the PG-approach, and we complement these with conditional lower bounds (in the sense of the fine-grained complexity framework). A special focus is put on enumeration and delay bounds, as well as the data complexity perspective. A main insight is that we can achieve optimal (or near optimal) algorithms with the PG-approach, but the delay for enumeration is rather high (linear in the database). We explore three successful approaches towards enumeration with sub-linear delay: super-linear preprocessing, approximations of the solution sets, and restricted classes of RPQs.}, author = {Casel, Katrin and Schmid, Markus L.}, booktitle = {International Conference on Database Theory (ICDT)}, keywords = {icdt katrincasel markuslschmid year2021}, title = {Fine-Grained Complexity of Regular Path Queries}, year = 2021 }
• 
  Bläsius, Thomas; Friedrich, Tobias; Göbel, Andreas; Levy, Jordi; Rothenberger, RalfThe Impact of Heterogeneity and Geometry on the Proof Complexity of Random Satisfiability. Symposium on Discrete Algorithms (SODA) 2021
  [ Abstract ] [ BibTeX ] [ Download ]
   
  Satisfiability is considered the canonical NP-complete problem and is used as a starting point for hardness reductions in theory, while in practice heuristic SAT solving algorithms can solve large-scale industrial SAT instances very efficiently. This disparity between theory and practice is believed to be a result of inherent properties of industrial SAT instances that make them tractable. Two characteristic properties seem to be prevalent in the majority of real-world SAT instances, heterogeneous degree distribution and locality. To understand the impact of these two properties on SAT, we study the proof complexity of random k-SAT models that allow to control heterogeneity and locality. Our findings show that heterogeneity alone does not make SAT easy as heterogeneous random k-SAT instances have superpolynomial resolution size. This implies intractability of these instances for modern SAT-solvers. On the other hand, modeling locality with an underlying geometry leads to small unsatisfiable subformulas, which can be found within polynomial time. A key ingredient for the result on geometric random k-SAT can be found in the complexity of higher-order Voronoi diagrams. As an additional technical contribution, we show an upper bound on the number of non-empty Voronoi regions, that holds for points with random positions in a very general setting. In particular, it covers arbitrary p-norms, higher dimensions, and weights affecting the area of influence of each point multiplicatively. Our bound is linear in the total weight. This is in stark contrast to quadratic lower bounds for the worst case.
  @inproceedings{blasius2021impact, abstract = {Satisfiability is considered the canonical NP-complete problem and is used as a starting point for hardness reductions in theory, while in practice heuristic SAT solving algorithms can solve large-scale industrial SAT instances very efficiently. This disparity between theory and practice is believed to be a result of inherent properties of industrial SAT instances that make them tractable. Two characteristic properties seem to be prevalent in the majority of real-world SAT instances, heterogeneous degree distribution and locality. To understand the impact of these two properties on SAT, we study the proof complexity of random k-SAT models that allow to control heterogeneity and locality. Our findings show that heterogeneity alone does not make SAT easy as heterogeneous random k-SAT instances have superpolynomial resolution size. This implies intractability of these instances for modern SAT-solvers. On the other hand, modeling locality with an underlying geometry leads to small unsatisfiable subformulas, which can be found within polynomial time. A key ingredient for the result on geometric random k-SAT can be found in the complexity of higher-order Voronoi diagrams. As an additional technical contribution, we show an upper bound on the number of non-empty Voronoi regions, that holds for points with random positions in a very general setting. In particular, it covers arbitrary p-norms, higher dimensions, and weights affecting the area of influence of each point multiplicatively. Our bound is linear in the total weight. This is in stark contrast to quadratic lower bounds for the worst case.}, author = {Bläsius, Thomas and Friedrich, Tobias and Göbel, Andreas and Levy, Jordi and Rothenberger, Ralf}, booktitle = {Symposium on Discrete Algorithms (SODA)}, keywords = {andreasgoebel jordilevy ralfrothenberger sat soda thomasblaesius tobiasfriedrich year2021}, title = {The Impact of Heterogeneity and Geometry on the Proof Complexity of Random Satisfiability}, year = 2021 }

2021

• 
  Doerr, Benjamin; Krejca, Martin S.A Simplified Run Time Analysis of the Univariate Marginal Distribution Algorithm on LeadingOnes. Theoretical Computer Science 2021: 121-128
  [ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
   
  With elementary means, we prove in this note a stronger run time guarantee for the univariate marginal distribution algorithm (UMDA) optimizing the LeadingOnes benchmark function in the desirable regime with low genetic drift. If the population size \(\mu\) is at least \(128 n \ln(n)\) and the selection rate \(\mu/\lambda\) is at most some constant less than \(\frac{1}{4e \approx 0.092\), then the UMDA samples the optimum within \(O\big(n\frac{\lambda}{log (\lambda/\mu)}\big)\) fitness evaluations with high probability. This improves over the previous \(O(n \lambda \log\lambda)\) guarantee that was obtained by Dang and Lehre (2015) via the deep level-based population method. With similar arguments as in our upper-bound analysis, we also obtain the first lower bound for this problem. Under similar assumptions, we prove that a bound of \(\Omega\big(lambda \frac{n - \log(n\lambda)}log (\lambda / \mu)}\big)\) fitness evaluations holds with high probability.
  @article{doerr2021simplified, abstract = {With elementary means, we prove in this note a stronger run time guarantee for the univariate marginal distribution algorithm (UMDA) optimizing the LeadingOnes benchmark function in the desirable regime with low genetic drift. If the population size \(\mu\) is at least \(128 n \ln(n)\) and the selection rate \(\mu/\lambda\) is at most some constant less than \(\frac{1}{4e} \approx 0.092\), then the UMDA samples the optimum within \(O\big(n\frac{\lambda}{\log (\lambda/\mu)}\big)\) fitness evaluations with high probability. This improves over the previous \(O(n \lambda \log\lambda)\) guarantee that was obtained by Dang and Lehre (2015) via the deep level-based population method. With similar arguments as in our upper-bound analysis, we also obtain the first lower bound for this problem. Under similar assumptions, we prove that a bound of \(\Omega\big(\lambda \frac{n - \log(n\lambda)}{\log (\lambda / \mu)}\big)\) fitness evaluations holds with high probability.}, author = {Doerr, Benjamin and Krejca, Martin S.}, journal = {Theoretical Computer Science}, keywords = {benjamindoerr martinskrejca tcs year2021}, pages = {121-128}, title = {A Simplified Run Time Analysis of the Univariate Marginal Distribution Algorithm on LeadingOnes}, volume = 851, year = 2021 }