6 Search Results for "Day, Robert"

Document
DOI: 10.4230/LIPIcs.MFCS.2022.38
Enumeration Classes Defined by Circuits

Authors: Nadia Creignou, Arnaud Durand, and Heribert Vollmer

Published in: LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)

Abstract
We refine the complexity landscape for enumeration problems by introducing very low classes defined by using Boolean circuits as enumerators. We locate well-known enumeration problems, e.g., from graph theory, Gray code enumeration, and propositional satisfiability in our classes. In this way we obtain a framework to distinguish between the complexity of different problems known to be in DelayP, for which a formal way of comparison was not possible to this day.
Cite as

Nadia Creignou, Arnaud Durand, and Heribert Vollmer. Enumeration Classes Defined by Circuits. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 38:1-38:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{creignou_et_al:LIPIcs.MFCS.2022.38,
  author =	{Creignou, Nadia and Durand, Arnaud and Vollmer, Heribert},
  title =	{{Enumeration Classes Defined by Circuits}},
  booktitle =	{47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
  pages =	{38:1--38:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-256-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{241},
  editor =	{Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.38},
  URN =		{urn:nbn:de:0030-drops-168364},
  doi =		{10.4230/LIPIcs.MFCS.2022.38},
  annote =	{Keywords: Computational complexity, enumeration problem, Boolean circuit}
}
Document
DOI: 10.4230/LIPIcs.SNAPL.2017.17
Migratory Typing: Ten Years Later

Authors: Sam Tobin-Hochstadt, Matthias Felleisen, Robert Findler, Matthew Flatt, Ben Greenman, Andrew M. Kent, Vincent St-Amour, T. Stephen Strickland, and Asumu Takikawa

Published in: LIPIcs, Volume 71, 2nd Summit on Advances in Programming Languages (SNAPL 2017)

Abstract
In this day and age, many developers work on large, untyped code repositories. Even if they are the creators of the code, they notice that they have to figure out the equivalent of method signatures every time they work on old code. This step is time consuming and error prone. Ten years ago, the two lead authors outlined a linguistic solution to this problem. Specifically they proposed the creation of typed twins for untyped programming languages so that developers could migrate scripts from the untyped world to a typed one in an incremental manner. Their programmatic paper also spelled out three guiding design principles concerning the acceptance of grown idioms, the soundness of mixed-typed programs, and the units of migration. This paper revisits this idea of a migratory type system as implemented for Racket. It explains how the design principles have been used to produce the Typed Racket twin and presents an assessment of the project's status, highlighting successes and failures.
Cite as

Sam Tobin-Hochstadt, Matthias Felleisen, Robert Findler, Matthew Flatt, Ben Greenman, Andrew M. Kent, Vincent St-Amour, T. Stephen Strickland, and Asumu Takikawa. Migratory Typing: Ten Years Later. In 2nd Summit on Advances in Programming Languages (SNAPL 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 71, pp. 17:1-17:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{tobinhochstadt_et_al:LIPIcs.SNAPL.2017.17,
  author =	{Tobin-Hochstadt, Sam and Felleisen, Matthias and Findler, Robert and Flatt, Matthew and Greenman, Ben and Kent, Andrew M. and St-Amour, Vincent and Strickland, T. Stephen and Takikawa, Asumu},
  title =	{{Migratory Typing: Ten Years Later}},
  booktitle =	{2nd Summit on Advances in Programming Languages (SNAPL 2017)},
  pages =	{17:1--17:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-032-3},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{71},
  editor =	{Lerner, Benjamin S. and Bod{\'\i}k, Rastislav and Krishnamurthi, Shriram},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SNAPL.2017.17},
  URN =		{urn:nbn:de:0030-drops-71202},
  doi =		{10.4230/LIPIcs.SNAPL.2017.17},
  annote =	{Keywords: design principles, type systems, gradual typing}
}
Document
DOI: 10.4230/DagRep.3.6.38
Virtual Realities (Dagstuhl Seminar 13241)

Authors: Guido Brunnett, Sabine Coquillart, Robert van Liere, and Gregory F. Welch

Published in: Dagstuhl Reports, Volume 3, Issue 6 (2013)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 13241 "Virtual Realities". The main goal of the five day seminar was to bring together leading experts and promising young researchers to discuss current challenges and future directions in the field of virtual and augmented reality. The seminar was organized as series of individual presentations and seven working groups. Abstracts of the presentations and working group reports are collected in this report.
Cite as

Guido Brunnett, Sabine Coquillart, Robert van Liere, and Gregory F. Welch. Virtual Realities (Dagstuhl Seminar 13241). In Dagstuhl Reports, Volume 3, Issue 6, pp. 38-66, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@Article{brunnett_et_al:DagRep.3.6.38,
  author =	{Brunnett, Guido and Coquillart, Sabine and van Liere, Robert and Welch, Gregory F.},
  title =	{{Virtual Realities (Dagstuhl Seminar 13241)}},
  pages =	{38--66},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2013},
  volume =	{3},
  number =	{6},
  editor =	{Brunnett, Guido and Coquillart, Sabine and van Liere, Robert and Welch, Gregory F.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.3.6.38},
  URN =		{urn:nbn:de:0030-drops-42579},
  doi =		{10.4230/DagRep.3.6.38},
  annote =	{Keywords: Virtual Reality, 3D Interaction, Presence, Human Factors}
}
Document
DOI: 10.4230/DagSemProc.08451.3
08451 Minutes of Open Problems Session

Authors: Robert Weibel

Published in: Dagstuhl Seminar Proceedings, Volume 8451, Representation, Analysis and Visualization of Moving Objects (2009)

Abstract
Summary of the open problems identified in a special session in the evening of the first day of Dagstuhl seminar 08451 on"Representation, Analysis and Visualization of Moving Objects".
Cite as

Robert Weibel. 08451 Minutes of Open Problems Session. In Representation, Analysis and Visualization of Moving Objects. Dagstuhl Seminar Proceedings, Volume 8451, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{weibel:DagSemProc.08451.3,
  author =	{Weibel, Robert},
  title =	{{08451 Minutes of Open Problems Session }},
  booktitle =	{Representation, Analysis and Visualization of Moving Objects},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{8451},
  editor =	{Wolfgang Bitterlich and J\"{o}rg-R\"{u}diger Sack and Monika Sester and Robert Weibel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.08451.3},
  URN =		{urn:nbn:de:0030-drops-18764},
  doi =		{10.4230/DagSemProc.08451.3},
  annote =	{Keywords: Moving objects, trajectory data mining}
}
Document
DOI: 10.4230/DagSemProc.06091.3
Die Another Day

Authors: Rudolf Fleischer

Published in: Dagstuhl Seminar Proceedings, Volume 6091, Data Structures (2006)

Abstract
The hydra was a many-headed monster from Greek mythology that could grow one or two new heads when one of its heads got cut off. It was the second task of Hercules to kill this monster. In an abstract sense a hydra can be modeled by a tree where the leaves are the heads, and when a head is cut off some subtrees get duplicated. Different hydra species differ by the location of subtrees to be duplicated and by the number of new subtrees grown in each step. Using some deep mathematics, it had been shown that two classes of rather restricted hydra species must always die, independent of the order in which heads are cut off. In this paper we provide an elementary proof which actually gives a complete classification of all hydra species as immortal or doomed. Now, if Hercules had known this...
Cite as

Rudolf Fleischer. Die Another Day. In Data Structures. Dagstuhl Seminar Proceedings, Volume 6091, pp. 1-8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{fleischer:DagSemProc.06091.3,
  author =	{Fleischer, Rudolf},
  title =	{{Die Another Day}},
  booktitle =	{Data Structures},
  pages =	{1--8},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6091},
  editor =	{Lars Arge and Robert Sedgewick and Dorothea Wagner},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.06091.3},
  URN =		{urn:nbn:de:0030-drops-7652},
  doi =		{10.4230/DagSemProc.06091.3},
  annote =	{Keywords: Hydra, Koenig's Lemma, Peano Arithmetic}
}
Document
DOI: 10.4230/DagSemProc.05011.9
Fair Payments for Efficient Allocations in Public Sector Combinatorial Auctions

Authors: Robert Day and S. Raghavan

Published in: Dagstuhl Seminar Proceedings, Volume 5011, Computing and Markets (2005)

Abstract
Motivated by the increasing use of auctions by government agencies, we consider the problem of fairly pricing public goods in a combinatorial auction. A well-known problem with the incentive-compatible Vickrey-Clarke-Groves (VCG) auction mechanism is that the resulting prices may not be in the core. Loosely speaking, this means the payments of the winners could be so low, that there are losing bidders who would have been willing to pay more than the payments of the winning bidders. Clearly, this ``unfair'' outcome is unacceptable for a public-sector auction. Proxy-based combinatorial auctions, in which each bidder submits several package bids to a proxy, result in efficient outcomes and bidder-Pareto-optimal core-payments by winners, thus offering a viable practical alternative to address this problem. This paper confronts two critical issues facing the proxy-auction. First, motivated to minimize a bidder's ability to benefit through strategic manipulation (through collusive agreement or unilateral action), we demonstrate the strength of a mechanism that minimizes total payments among all possible proxy auction outcomes, narrowing the previously broad solution concept. Secondly, we address the computational difficulties of achieving these outcomes with a constraint-generation approach, promising to broaden the range of applications for which the proxy-auction achieves a comfortably rapid solution.
Cite as

Robert Day and S. Raghavan. Fair Payments for Efficient Allocations in Public Sector Combinatorial Auctions. In Computing and Markets. Dagstuhl Seminar Proceedings, Volume 5011, pp. 1-29, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)

Copy BibTex To Clipboard

@InProceedings{day_et_al:DagSemProc.05011.9,
  author =	{Day, Robert and Raghavan, S.},
  title =	{{Fair Payments for Efficient Allocations in Public Sector Combinatorial Auctions}},
  booktitle =	{Computing and Markets},
  pages =	{1--29},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{5011},
  editor =	{Daniel Lehmann and Rudolf M\"{u}ller and Tuomas Sandholm},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.05011.9},
  URN =		{urn:nbn:de:0030-drops-1832},
  doi =		{10.4230/DagSemProc.05011.9},
  annote =	{Keywords: auctions , core , bidder-Pareto-optimal , constraint generation , VCG payments , proxy auctions , combinatorial auctions}
}
  • Refine by Author
  • 1 Brunnett, Guido
  • 1 Coquillart, Sabine
  • 1 Creignou, Nadia
  • 1 Day, Robert
  • 1 Durand, Arnaud
  • Show More...

  • Refine by Classification
  • 1 Theory of computation → Circuit complexity
  • 1 Theory of computation → Complexity classes

  • Refine by Keyword
  • 1 3D Interaction
  • 1 Boolean circuit
  • 1 Computational complexity
  • 1 Human Factors
  • 1 Hydra
  • Show More...

  • Refine by Type
  • 6 document

  • Refine by Publication Year
  • 1 2005
  • 1 2006
  • 1 2009
  • 1 2013
  • 1 2017
  • 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