7 Search Results for "Schulman, Leonard"

Document
DOI: 10.4230/LIPIcs.WABI.2024.12
Reconstructing Rearrangement Phylogenies of Natural Genomes

Authors: Leonard Bohnenkämper, Jens Stoye, and Daniel Dörr

Published in: LIPIcs, Volume 312, 24th International Workshop on Algorithms in Bioinformatics (WABI 2024)

Abstract
We study the classical problem of inferring ancestral genomes from a set of extant genomes under a given phylogeny, known as the Small Parsimony Problem (SPP). Genomes are represented as sequences of oriented markers, organized in one or more linear or circular chromosomes. Any marker may appear in several copies, without restriction on orientation or genomic location, known as the natural genomes model. Evolutionary events along the branches of the phylogeny encompass large scale rearrangements, including segmental inversions, translocations, gain and loss (DCJ-indel model). Even under simpler rearrangement models, such as the classical breakpoint model without duplicates, the SPP is computationally intractable. Nevertheless, the SPP for natural genomes under the DCJ-indel model has been studied recently, with limited success. Here, we improve on that earlier work, giving a highly optimized ILP that is able to solve the SPP for sufficiently small phylogenies and gene families. A notable improvement w.r.t. the previous result is an optimized way of handling both circular and linear chromosomes. This is especially relevant to the SPP, since the chromosomal structure of ancestral genomes is unknown and the solution space for this chromosomal structure is typically large. We benchmark our method on simulated and real data. On simulated phylogenies we observe a considerable performance improvement on problems that include linear chromosomes. And even when the ground truth contains only one circular chromosome per genome, our method outperforms its predecessor due to its optimized handling of the solution space. The practical advantage becomes also visible in an analysis of seven Anopheles taxa.
Cite as

Leonard Bohnenkämper, Jens Stoye, and Daniel Dörr. Reconstructing Rearrangement Phylogenies of Natural Genomes. In 24th International Workshop on Algorithms in Bioinformatics (WABI 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 312, pp. 12:1-12:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bohnenkamper_et_al:LIPIcs.WABI.2024.12,
  author =	{Bohnenk\"{a}mper, Leonard and Stoye, Jens and D\"{o}rr, Daniel},
  title =	{{Reconstructing Rearrangement Phylogenies of Natural Genomes}},
  booktitle =	{24th International Workshop on Algorithms in Bioinformatics (WABI 2024)},
  pages =	{12:1--12:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-340-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{312},
  editor =	{Pissis, Solon P. and Sung, Wing-Kin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2024.12},
  URN =		{urn:nbn:de:0030-drops-206564},
  doi =		{10.4230/LIPIcs.WABI.2024.12},
  annote =	{Keywords: genome rearrangement, ancestral reconstruction, small parsimony, integer linear programming, double-cut-and-join}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.FSTTCS.2023.3
Computational and Information-Theoretic Questions from Causal Inference (Invited Talk)

Authors: Leonard J. Schulman

Published in: LIPIcs, Volume 284, 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023)

Abstract
Data, for the most part, is used in order to inform potential interventions: whether by individuals (decisions about education or employment), government (public health, environmental regulation, infrastructure investment) or business. The most common data analysis tools are those which identify correlations among variables - think of regression or of clustering. However, some famous paradoxes illustrate the futility of relying on correlations alone without a model for the causal relationships between variables. Historically, causality has been teased apart from correlation through controlled experiments. But for a variety of reasons - cost, ethical constraints, or uniqueness of the system - we must often make do with passive observation alone. A theory based upon directed graphical models has been developed over the past three decades, which in some situations, enables statistically defensible causal inference even in the absence of controlled experiments. Yet "some situations" is rather fewer than one would like. This limitation spurs a range of research questions. In this talk I will describe a couple of causality paradoxes along with how they are captured within the graphical model framework; this will lead naturally toward some of the computational and information-theoretic questions which arise in the theory.
Cite as

Leonard J. Schulman. Computational and Information-Theoretic Questions from Causal Inference (Invited Talk). In 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 284, p. 3:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{schulman:LIPIcs.FSTTCS.2023.3,
  author =	{Schulman, Leonard J.},
  title =	{{Computational and Information-Theoretic Questions from Causal Inference}},
  booktitle =	{43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023)},
  pages =	{3:1--3:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-304-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{284},
  editor =	{Bouyer, Patricia and Srinivasan, Srikanth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2023.3},
  URN =		{urn:nbn:de:0030-drops-193769},
  doi =		{10.4230/LIPIcs.FSTTCS.2023.3},
  annote =	{Keywords: Causal Inference, Bayesian Networks}
}
Document
DOI: 10.4230/LIPIcs.CCC.2020.11
Palette-Alternating Tree Codes

Authors: Gil Cohen and Shahar Samocha

Published in: LIPIcs, Volume 169, 35th Computational Complexity Conference (CCC 2020)

Abstract
A tree code is an edge-coloring of the complete infinite binary tree such that every two nodes of equal depth have a fraction - bounded away from 0 - of mismatched colors between the corresponding paths to their least common ancestor. Tree codes were introduced in a seminal work by Schulman [Schulman, 1993] and serve as a key ingredient in almost all deterministic interactive coding schemes. The number of colors effects the coding scheme’s rate. It is shown that 4 is precisely the least number of colors for which tree codes exist. Thus, tree-code-based coding schemes cannot achieve rate larger than 1/2. To overcome this barrier, a relaxed notion called palette-alternating tree codes is introduced, in which the number of colors can depend on the layer. We prove the existence of such constructs in which most layers use 2 colors - the bare minimum. The distance-rate tradeoff we obtain matches the Gilbert-Varshamov bound. Based on palette-alternating tree codes, we devise a deterministic interactive coding scheme against adversarial errors that approaches capacity. To analyze our protocol, we prove a structural result on the location of failed communication-rounds induced by the error pattern enforced by the adversary. Our coding scheme is efficient given an explicit palette-alternating tree code and serves as an alternative to the scheme obtained by [R. Gelles et al., 2016].
Cite as

Gil Cohen and Shahar Samocha. Palette-Alternating Tree Codes. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 11:1-11:29, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{cohen_et_al:LIPIcs.CCC.2020.11,
  author =	{Cohen, Gil and Samocha, Shahar},
  title =	{{Palette-Alternating Tree Codes}},
  booktitle =	{35th Computational Complexity Conference (CCC 2020)},
  pages =	{11:1--11:29},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-156-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{169},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2020.11},
  URN =		{urn:nbn:de:0030-drops-125632},
  doi =		{10.4230/LIPIcs.CCC.2020.11},
  annote =	{Keywords: Tree Codes, Coding Theory, Interactive Coding Scheme}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2018.59
Learning Dynamics and the Co-Evolution of Competing Sexual Species

Authors: Georgios Piliouras and Leonard J. Schulman

Published in: LIPIcs, Volume 94, 9th Innovations in Theoretical Computer Science Conference (ITCS 2018)

Abstract
We analyze a stylized model of co-evolution between any two purely competing species (e.g., host and parasite), both sexually reproducing. Similarly to a recent model [Livnat et al. FOCS'14] the fitness of an individual depends on whether the truth assignments on n variables that reproduce through recombination satisfy a particular Boolean function. Whereas in the original model a satisfying assignment always confers a small evolutionary advantage, in our model the two species are in an evolutionary race with the parasite enjoying the advantage if the value of its Boolean function matches its host, and the host wishing to mismatch its parasite. Surprisingly, this model makes a simple and robust behavioral prediction. The typical system behavior is periodic. These cycles stay bounded away from the boundary and thus, learning-dynamics competition between sexual species can provide an explanation for genetic diversity. This explanation is due solely to the natural selection process. No mutations, environmental changes, etc., need be invoked. The game played at the gene level may have many Nash equilibria with widely diverse fitness levels. Nevertheless, sexual evolution leads to gene coordination that implements an optimal strategy, i.e., an optimal population mixture, at the species level. Namely, the play of the many "selfish genes" implements a time-averaged correlated equilibrium where the average fitness of each species is exactly equal to its value in the two species zero-sum competition. Our analysis combines tools from game theory, dynamical systems and Boolean functions to establish a novel class of conservative dynamical systems.
Cite as

Georgios Piliouras and Leonard J. Schulman. Learning Dynamics and the Co-Evolution of Competing Sexual Species. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 59:1-59:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{piliouras_et_al:LIPIcs.ITCS.2018.59,
  author =	{Piliouras, Georgios and Schulman, Leonard J.},
  title =	{{Learning Dynamics and the Co-Evolution of Competing Sexual Species}},
  booktitle =	{9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
  pages =	{59:1--59:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-060-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{94},
  editor =	{Karlin, Anna R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.59},
  URN =		{urn:nbn:de:0030-drops-83637},
  doi =		{10.4230/LIPIcs.ITCS.2018.59},
  annote =	{Keywords: Dynamical Systems, Potential Game, Team Zero-Sum Game, Boolean Functions, Replicator Dynamics}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2017.56
The Duality Gap for Two-Team Zero-Sum Games

Authors: Leonard Schulman and Umesh V. Vazirani

Published in: LIPIcs, Volume 67, 8th Innovations in Theoretical Computer Science Conference (ITCS 2017)

Abstract
We consider multiplayer games in which the players fall in two teams of size k, with payoffs equal within, and of opposite sign across, the two teams. In the classical case of k=1, such zero-sum games possess a unique value, independent of order of play, due to the von Neumann minimax theorem. However, this fails for all k>1; we can measure this failure by a duality gap, which quantifies the benefit of being the team to commit last to its strategy. In our main result we show that the gap equals 2(1-2^{1-k}) for m=2 and 2(1-\m^{-(1-o(1))k}) for m>2, with m being the size of the action space of each player. At a finer level, the cost to a team of individual players acting independently while the opposition employs joint randomness is 1-2^{1-k} for k=2, and 1-\m^{-(1-o(1))k} for m>2. This class of multiplayer games, apart from being a natural bridge between two-player zero-sum games and general multiplayer games, is motivated from Biology (the weak selection model of evolution) and Economics (players with shared utility but poor coordination).
Cite as

Leonard Schulman and Umesh V. Vazirani. The Duality Gap for Two-Team Zero-Sum Games. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 56:1-56:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{schulman_et_al:LIPIcs.ITCS.2017.56,
  author =	{Schulman, Leonard and Vazirani, Umesh V.},
  title =	{{The Duality Gap for Two-Team Zero-Sum Games}},
  booktitle =	{8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
  pages =	{56:1--56:8},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-029-3},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{67},
  editor =	{Papadimitriou, Christos H.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.56},
  URN =		{urn:nbn:de:0030-drops-81429},
  doi =		{10.4230/LIPIcs.ITCS.2017.56},
  annote =	{Keywords: multi-player games, duality gap, zero-sum games, evolution}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2015.543
Allocation of Divisible Goods Under Lexicographic Preferences

Authors: Leonard J. Schulman and Vijay V. Vazirani

Published in: LIPIcs, Volume 45, 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)

Abstract
We present a simple and natural non-pricing mechanism for allocating divisible goods among strategic agents having lexicographic preferences. Our mechanism has favorable properties of strategy-proofness (incentive compatibility). In addition (and even when extended to the case of Leontief bundles) it enjoys Pareto efficiency, envy-freeness, and time efficiency.
Cite as

Leonard J. Schulman and Vijay V. Vazirani. Allocation of Divisible Goods Under Lexicographic Preferences. In 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 45, pp. 543-559, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{schulman_et_al:LIPIcs.FSTTCS.2015.543,
  author =	{Schulman, Leonard J. and Vazirani, Vijay V.},
  title =	{{Allocation of Divisible Goods Under Lexicographic Preferences}},
  booktitle =	{35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)},
  pages =	{543--559},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-97-2},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{45},
  editor =	{Harsha, Prahladh and Ramalingam, G.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2015.543},
  URN =		{urn:nbn:de:0030-drops-56279},
  doi =		{10.4230/LIPIcs.FSTTCS.2015.543},
  annote =	{Keywords: Mechanism design, lexicographic preferences, strategyproof, Pareto optimal, incentive compatible}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2008.1741
Solvency Games

Authors: Noam Berger, Nevin Kapur, Leonard Schulman, and Vijay Vazirani

Published in: LIPIcs, Volume 2, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2008)

Abstract
We study the decision theory of a maximally risk-averse investor --- one whose objective, in the face of stochastic uncertainties, is to minimize the probability of ever going broke. With a view to developing the mathematical basics of such a theory, we start with a very simple model and obtain the following results: a characterization of best play by investors; an explanation of why poor and rich players may have different best strategies; an explanation of why expectation-maximization is not necessarily the best strategy even for rich players. For computation of optimal play, we show how to apply the Value Iteration method, and prove a bound on its convergence rate.
Cite as

Noam Berger, Nevin Kapur, Leonard Schulman, and Vijay Vazirani. Solvency Games. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 2, pp. 61-72, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{berger_et_al:LIPIcs.FSTTCS.2008.1741,
  author =	{Berger, Noam and Kapur, Nevin and Schulman, Leonard and Vazirani, Vijay},
  title =	{{Solvency Games}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science},
  pages =	{61--72},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-08-8},
  ISSN =	{1868-8969},
  year =	{2008},
  volume =	{2},
  editor =	{Hariharan, Ramesh and Mukund, Madhavan and Vinay, V},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2008.1741},
  URN =		{urn:nbn:de:0030-drops-17419},
  doi =		{10.4230/LIPIcs.FSTTCS.2008.1741},
  annote =	{Keywords: Decision making under uncertainity, multi-arm bandit problems, game theory}
}
  • Refine by Author
  • 3 Schulman, Leonard J.
  • 2 Schulman, Leonard
  • 1 Berger, Noam
  • 1 Bohnenkämper, Leonard
  • 1 Cohen, Gil
  • Show More...

  • Refine by Classification

  • Refine by Keyword
  • 1 Bayesian Networks
  • 1 Boolean Functions
  • 1 Causal Inference
  • 1 Coding Theory
  • 1 Decision making under uncertainity
  • Show More...

  • Refine by Type
  • 7 document

  • Refine by Publication Year
  • 1 2008
  • 1 2015
  • 1 2017
  • 1 2018
  • 1 2020
  • 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 About DROPS Imprint Privacy Contact