4 Search Results for "Schulman, Leonard J."


Document
Invited Talk
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
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
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
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}
}
  • Refine by Author
  • 3 Schulman, Leonard J.
  • 1 Cohen, Gil
  • 1 Piliouras, Georgios
  • 1 Samocha, Shahar
  • 1 Vazirani, Vijay V.

  • Refine by Classification
  • 1 Computing methodologies → Bayesian network models
  • 1 Computing methodologies → Causal reasoning and diagnostics
  • 1 Theory of computation → Error-correcting codes

  • Refine by Keyword
  • 1 Bayesian Networks
  • 1 Boolean Functions
  • 1 Causal Inference
  • 1 Coding Theory
  • 1 Dynamical Systems
  • Show More...

  • Refine by Type
  • 4 document

  • Refine by Publication Year
  • 1 2015
  • 1 2018
  • 1 2020
  • 1 2023

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