2 Search Results for "Shan, Liren"

Document
DOI: 10.4230/LIPIcs.FORC.2026.19
A Machine Learning Theory Perspective on Strategic Litigation

Authors: Melissa Dutz, Han Shao, Avrim Blum, and Aloni Cohen

Published in: LIPIcs, Volume 368, 7th Symposium on Foundations of Responsible Computing (FORC 2026)

Abstract
Strategic litigation involves bringing a case to court with the goal of having an impact beyond resolving the particular dispute at hand. In a common law system, one way a case may have far-reaching impact is by establishing new legal precedent that later courts must follow. In this paper, we explore strategic litigation from the perspective of machine learning theory. We consider an abstract model of a common law legal system where a lower court decides new cases by applying a decision rule learned from a higher court’s past rulings. In this model, we explore the power of a strategic litigator, who strategically brings cases to the higher court to influence the decision rule applied by the lower court in future cases. We explore questions including: What impact can a strategic litigator have? Which cases should a strategic litigator bring to court? Does it ever make sense for a strategic litigator to bring a case when they are sure the court will rule against them? We show that this strategic case selection problem has interesting structure, with even simple settings exhibiting counterintuitive phenomena. When cases are represented by points in one dimension and the lower court’s learning algorithm is nearest neighbor, or as points in d dimensions and the lower court’s learning algorithm is a support vector machine, we characterize the set of inducible decision rules and develop algorithms for selecting an optimal set of cases to bring to the higher court given the strategic litigator’s objectives.
Cite as

Melissa Dutz, Han Shao, Avrim Blum, and Aloni Cohen. A Machine Learning Theory Perspective on Strategic Litigation. In 7th Symposium on Foundations of Responsible Computing (FORC 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 368, pp. 19:1-19:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{dutz_et_al:LIPIcs.FORC.2026.19,
  author =	{Dutz, Melissa and Shao, Han and Blum, Avrim and Cohen, Aloni},
  title =	{{A Machine Learning Theory Perspective on Strategic Litigation}},
  booktitle =	{7th Symposium on Foundations of Responsible Computing (FORC 2026)},
  pages =	{19:1--19:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-419-2},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{368},
  editor =	{Lin, Huijia (Rachel)},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FORC.2026.19},
  URN =		{urn:nbn:de:0030-drops-259921},
  doi =		{10.4230/LIPIcs.FORC.2026.19},
  annote =	{Keywords: Strategic Litigation, Machine Learning Theory, Law}
}
Document
DOI: 10.4230/LIPIcs.ESA.2023.32
Approximation Algorithm for Norm Multiway Cut

Authors: Charlie Carlson, Jafar Jafarov, Konstantin Makarychev, Yury Makarychev, and Liren Shan

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

Abstract
We consider variants of the classic Multiway Cut problem. Multiway Cut asks to partition a graph G into k parts so as to separate k given terminals. Recently, Chandrasekaran and Wang (ESA 2021) introduced 𝓁_p-norm Multiway Cut, a generalization of the problem, in which the goal is to minimize the 𝓁_p norm of the edge boundaries of k parts. We provide an O(log^{1/2} nlog^{1/2+1/p} k) approximation algorithm for this problem, improving upon the approximation guarantee of O(log^{3/2} n log^{1/2} k) due to Chandrasekaran and Wang. We also introduce and study Norm Multiway Cut, a further generalization of Multiway Cut. We assume that we are given access to an oracle, which answers certain queries about the norm. We present an O(log^{1/2} n log^{7/2} k) approximation algorithm with a weaker oracle and an O(log^{1/2} n log^{5/2} k) approximation algorithm with a stronger oracle. Additionally, we show that without any oracle access, there is no n^{1/4-ε} approximation algorithm for every ε > 0 assuming the Hypergraph Dense-vs-Random Conjecture.
Cite as

Charlie Carlson, Jafar Jafarov, Konstantin Makarychev, Yury Makarychev, and Liren Shan. Approximation Algorithm for Norm Multiway Cut. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 32:1-32:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{carlson_et_al:LIPIcs.ESA.2023.32,
  author =	{Carlson, Charlie and Jafarov, Jafar and Makarychev, Konstantin and Makarychev, Yury and Shan, Liren},
  title =	{{Approximation Algorithm for Norm Multiway Cut}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{32:1--32:14},
  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.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.32},
  URN =		{urn:nbn:de:0030-drops-186854},
  doi =		{10.4230/LIPIcs.ESA.2023.32},
  annote =	{Keywords: Multiway cut, Approximation algorithms}
}
  • Refine by Type
  • 2 Document/PDF
  • 1 Document/HTML

  • Refine by Publication Year
  • 1 2026
  • 1 2023

  • Refine by Author
  • 1 Blum, Avrim
  • 1 Carlson, Charlie
  • 1 Cohen, Aloni
  • 1 Dutz, Melissa
  • 1 Jafarov, Jafar
  • Show More...

  • Refine by Series/Journal
  • 2 LIPIcs

  • Refine by Classification
  • 1 Theory of computation → Algorithmic game theory
  • 1 Theory of computation → Approximation algorithms analysis
  • 1 Theory of computation → Facility location and clustering
  • 1 Theory of computation → Machine learning theory

  • Refine by Keyword
  • 1 Approximation algorithms
  • 1 Law
  • 1 Machine Learning Theory
  • 1 Multiway cut
  • 1 Strategic Litigation

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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