11 Search Results for "Wang, Peter"


Document
Distributed Sketching Lower Bounds for k-Edge Connected Spanning Subgraphs, BFS Trees, and LCL Problems

Authors: Peter Robinson

Published in: LIPIcs, Volume 281, 37th International Symposium on Distributed Computing (DISC 2023)


Abstract
We investigate graph problems in the distributed sketching model, where each node sends a single message to a referee who computes the output. We define a class of graphs and give a framework for proving lower bounds for certain embeddable problems, which leads to several new results: First, we present a tight lower bound of Ω(n) bits for the message size of computing a breadth-first search (BFS) tree. For locally-checkable labeling (LCL) problems, we show that verifying whether a given vertex labeling forms a weak 2-coloring requires messages of Ω(n^{1/3}log^{2/3}n) bits, and the same lower bound holds for verifying whether a subset of nodes forms a maximal independent set. We also prove that computing a k-edge connected spanning subgraph (k-ECSS) requires messages of size at least Ω(klog²(n/k)), which is tight up to a logarithmic factor. To show these results, we define a simultaneous multiparty (SMP) model of communication complexity, where the players obtain certain subgraphs as their input, and develop a generic embedding argument that allows us to prove lower bounds for the graph sketching model by using reductions from the SMP model. We point out that these results also extend to single-round algorithms in the broadcast congested clique. We also (nearly) settle the space complexity of the k-ECSS problem in the streaming model by extending the work of Kapralov, Nelson, Pachoki, Wang, and Woodruff (FOCS 2017): We prove a communication complexity lower bound for a direct sum variant of the UR^⊂_k problem and show that this implies Ω(k nlog²(n/k)) bits of memory for computing a k-ECSS. This is known to be optimal up to a logarithmic factor.

Cite as

Peter Robinson. Distributed Sketching Lower Bounds for k-Edge Connected Spanning Subgraphs, BFS Trees, and LCL Problems. In 37th International Symposium on Distributed Computing (DISC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 281, pp. 32:1-32:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{robinson:LIPIcs.DISC.2023.32,
  author =	{Robinson, Peter},
  title =	{{Distributed Sketching Lower Bounds for k-Edge Connected Spanning Subgraphs, BFS Trees, and LCL Problems}},
  booktitle =	{37th International Symposium on Distributed Computing (DISC 2023)},
  pages =	{32:1--32:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-301-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{281},
  editor =	{Oshman, Rotem},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2023.32},
  URN =		{urn:nbn:de:0030-drops-191589},
  doi =		{10.4230/LIPIcs.DISC.2023.32},
  annote =	{Keywords: Distributed graph algorithm, graph sketching, streaming}
}
Document
Short Paper
Application of GIS in Public Health Practice: A Consortium’s Approach to Tackling Travel Delays in Obstetric Emergencies in Urban Areas (Short Paper)

Authors: Jia Wang, Itohan Osayande, Peter M. Macharia, Prestige Tatenda Makanga, Kerry L. M. Wong, Tope Olubodun, Uchenna Gwacham-Anisiobi, Olakunmi Ogunyemi, Abimbola Olaniran, Ibukun-Oluwa O. Abejirinde, Lenka Beňová, Bosede B. Afolabi, and Aduragbemi Banke-Thomas

Published in: LIPIcs, Volume 277, 12th International Conference on Geographic Information Science (GIScience 2023)


Abstract
Geographic Information System (GIS) has become an effective and reliable tool for researchers, policymakers, and decision-makers to map health outcomes and inform targeted planning, evaluation, and monitoring. With the advent of big data-enabled GIS, researchers can now identify disparities and spatial inequalities in health at more granular levels, enabling them to provide more accurate and robust services and products for healthcare. This paper aims to showcase the progress of the On Tackling In-transit Delays for Mothers in Emergency (OnTIME) project, which is a unique collaborative effort between academia, policymakers, and industrial partners. The paper demonstrates how the limitations of traditional spatial accessibility models and data gaps have been overcome by combining GIS and big data to map the geographic accessibility and coverage of health facilities capable of providing emergency obstetric care (EmOC) in conurbations in Africa. The OnTIME project employs various GIS technologies and concepts, such as big spatial data, spatial databases, and public participation geographic information systems (PPGIS). We provide an overview of these concepts in relation to the OnTIME project to demonstrate the application of GIS in public health practice.

Cite as

Jia Wang, Itohan Osayande, Peter M. Macharia, Prestige Tatenda Makanga, Kerry L. M. Wong, Tope Olubodun, Uchenna Gwacham-Anisiobi, Olakunmi Ogunyemi, Abimbola Olaniran, Ibukun-Oluwa O. Abejirinde, Lenka Beňová, Bosede B. Afolabi, and Aduragbemi Banke-Thomas. Application of GIS in Public Health Practice: A Consortium’s Approach to Tackling Travel Delays in Obstetric Emergencies in Urban Areas (Short Paper). In 12th International Conference on Geographic Information Science (GIScience 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 277, pp. 79:1-79:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{wang_et_al:LIPIcs.GIScience.2023.79,
  author =	{Wang, Jia and Osayande, Itohan and Macharia, Peter M. and Makanga, Prestige Tatenda and Wong, Kerry L. M. and Olubodun, Tope and Gwacham-Anisiobi, Uchenna and Ogunyemi, Olakunmi and Olaniran, Abimbola and Abejirinde, Ibukun-Oluwa O. and Be\v{n}ov\'{a}, Lenka and Afolabi, Bosede B. and Banke-Thomas, Aduragbemi},
  title =	{{Application of GIS in Public Health Practice: A Consortium’s Approach to Tackling Travel Delays in Obstetric Emergencies in Urban Areas}},
  booktitle =	{12th International Conference on Geographic Information Science (GIScience 2023)},
  pages =	{79:1--79:6},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-288-4},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{277},
  editor =	{Beecham, Roger and Long, Jed A. and Smith, Dianna and Zhao, Qunshan and Wise, Sarah},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.GIScience.2023.79},
  URN =		{urn:nbn:de:0030-drops-189748},
  doi =		{10.4230/LIPIcs.GIScience.2023.79},
  annote =	{Keywords: GIS, Public Health, Accessibility, OnTIME, EmOC, Public Participation GIS, Big Data, Google}
}
Document
Enabling Preserving Bisimulation Equivalence

Authors: Rob van Glabbeek, Peter Höfner, and Weiyou Wang

Published in: LIPIcs, Volume 203, 32nd International Conference on Concurrency Theory (CONCUR 2021)


Abstract
Most fairness assumptions used for verifying liveness properties are criticised for being too strong or unrealistic. On the other hand, justness, arguably the minimal fairness assumption required for the verification of liveness properties, is not preserved by classical semantic equivalences, such as strong bisimilarity. To overcome this deficiency, we introduce a finer alternative to strong bisimilarity, called enabling preserving bisimilarity. We prove that this equivalence is justness-preserving and a congruence for all standard operators, including parallel composition.

Cite as

Rob van Glabbeek, Peter Höfner, and Weiyou Wang. Enabling Preserving Bisimulation Equivalence. In 32nd International Conference on Concurrency Theory (CONCUR 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 203, pp. 33:1-33:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{vanglabbeek_et_al:LIPIcs.CONCUR.2021.33,
  author =	{van Glabbeek, Rob and H\"{o}fner, Peter and Wang, Weiyou},
  title =	{{Enabling Preserving Bisimulation Equivalence}},
  booktitle =	{32nd International Conference on Concurrency Theory (CONCUR 2021)},
  pages =	{33:1--33:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-203-7},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{203},
  editor =	{Haddad, Serge and Varacca, Daniele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2021.33},
  URN =		{urn:nbn:de:0030-drops-144107},
  doi =		{10.4230/LIPIcs.CONCUR.2021.33},
  annote =	{Keywords: bisimilarity, liveness properties, fairness assumptions, process algebra}
}
Document
Fast and Effective Techniques for T-Count Reduction via Spider Nest Identities

Authors: Niel de Beaudrap, Xiaoning Bian, and Quanlong Wang

Published in: LIPIcs, Volume 158, 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020)


Abstract
In fault-tolerant quantum computing systems, realising (approximately) universal quantum computation is usually described in terms of realising Clifford+T operations, which is to say a circuit of CNOT, Hadamard, and π/2-phase rotations, together with T operations (π/4-phase rotations). For many error correcting codes, fault-tolerant realisations of Clifford operations are significantly less resource-intensive than those of T gates, which motivates finding ways to realise the same transformation involving T-count (the number of T gates involved) which is as low as possible. Investigations into this problem [Matthew Amy et al., 2013; Gosset et al., 2014; Matthew Amy et al., 2014; Matthew Amy et al., 2018; Earl T. Campbell and Mark Howard, 2017; Matthew Amy and Michele Mosca, 2019] has led to observations that this problem is closely related to NP-hard tensor decomposition problems [Luke E. Heyfron and Earl T. Campbell, 2018] and is tantamount to the difficult problem of decoding exponentially long Reed-Muller codes [Matthew Amy and Michele Mosca, 2019]. This problem then presents itself as one for which must be content in practise with approximate optimisation, in which one develops an array of tactics to be deployed through some pragmatic strategy. In this vein, we describe techniques to reduce the T-count, based on the effective application of "spider nest identities": easily recognised products of parity-phase operations which are equivalent to the identity operation. We demonstrate the effectiveness of such techniques by obtaining improvements in the T-counts of a number of circuits, in run-times which are typically less than the time required to make a fresh cup of coffee.

Cite as

Niel de Beaudrap, Xiaoning Bian, and Quanlong Wang. Fast and Effective Techniques for T-Count Reduction via Spider Nest Identities. In 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 158, pp. 11:1-11:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{debeaudrap_et_al:LIPIcs.TQC.2020.11,
  author =	{de Beaudrap, Niel and Bian, Xiaoning and Wang, Quanlong},
  title =	{{Fast and Effective Techniques for T-Count Reduction via Spider Nest Identities}},
  booktitle =	{15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020)},
  pages =	{11:1--11:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-146-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{158},
  editor =	{Flammia, Steven T.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2020.11},
  URN =		{urn:nbn:de:0030-drops-120705},
  doi =		{10.4230/LIPIcs.TQC.2020.11},
  annote =	{Keywords: T-count, Parity-phase operations, Phase gadgets, Clifford hierarchy, ZX calculus}
}
Document
The Complexity of Packing Edge-Disjoint Paths

Authors: Jan Dreier, Janosch Fuchs, Tim A. Hartmann, Philipp Kuinke, Peter Rossmanith, Bjoern Tauer, and Hung-Lung Wang

Published in: LIPIcs, Volume 148, 14th International Symposium on Parameterized and Exact Computation (IPEC 2019)


Abstract
We introduce and study the complexity of Path Packing. Given a graph G and a list of paths, the task is to embed the paths edge-disjoint in G. This generalizes the well known Hamiltonian-Path problem. Since Hamiltonian Path is efficiently solvable for graphs of small treewidth, we study how this result translates to the much more general Path Packing. On the positive side, we give an FPT-algorithm on trees for the number of paths as parameter. Further, we give an XP-algorithm with the combined parameters maximal degree, number of connected components and number of nodes of degree at least three. Surprisingly the latter is an almost tight result by runtime and parameterization. We show an ETH lower bound almost matching our runtime. Moreover, if two of the three values are constant and one is unbounded the problem becomes NP-hard. Further, we study restrictions to the given list of paths. On the positive side, we present an FPT-algorithm parameterized by the sum of the lengths of the paths. Packing paths of length two is polynomial time solvable, while packing paths of length three is NP-hard. Finally, even the spacial case Exact Path Packing where the paths have to cover every edge in G exactly once is already NP-hard for two paths on 4-regular graphs.

Cite as

Jan Dreier, Janosch Fuchs, Tim A. Hartmann, Philipp Kuinke, Peter Rossmanith, Bjoern Tauer, and Hung-Lung Wang. The Complexity of Packing Edge-Disjoint Paths. In 14th International Symposium on Parameterized and Exact Computation (IPEC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 148, pp. 10:1-10:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{dreier_et_al:LIPIcs.IPEC.2019.10,
  author =	{Dreier, Jan and Fuchs, Janosch and Hartmann, Tim A. and Kuinke, Philipp and Rossmanith, Peter and Tauer, Bjoern and Wang, Hung-Lung},
  title =	{{The Complexity of Packing Edge-Disjoint Paths}},
  booktitle =	{14th International Symposium on Parameterized and Exact Computation (IPEC 2019)},
  pages =	{10:1--10:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-129-0},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{148},
  editor =	{Jansen, Bart M. P. and Telle, Jan Arne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2019.10},
  URN =		{urn:nbn:de:0030-drops-114710},
  doi =		{10.4230/LIPIcs.IPEC.2019.10},
  annote =	{Keywords: parameterized complexity, embedding, packing, covering, Hamiltonian path, unary binpacking, path-perfect graphs}
}
Document
Two variable fragment of Term Modal Logic

Authors: Anantha Padmanabha and R. Ramanujam

Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)


Abstract
Term modal logics (TML) are modal logics with unboundedly many modalities, with quantification over modal indices, so that we can have formulas of the form Exists y Forall x (Box_x P(x,y) implies Diamond_y P(y,x)). Like First order modal logic, TML is also "notoriously" undecidable, in the sense that even very simple fragments are undecidable. In this paper, we show the decidability of one interesting fragment, that of two variable TML. This is in contrast to two-variable First order modal logic, which is undecidable.

Cite as

Anantha Padmanabha and R. Ramanujam. Two variable fragment of Term Modal Logic. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 30:1-30:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{padmanabha_et_al:LIPIcs.MFCS.2019.30,
  author =	{Padmanabha, Anantha and Ramanujam, R.},
  title =	{{Two variable fragment of Term Modal Logic}},
  booktitle =	{44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
  pages =	{30:1--30:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-117-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{138},
  editor =	{Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.30},
  URN =		{urn:nbn:de:0030-drops-109741},
  doi =		{10.4230/LIPIcs.MFCS.2019.30},
  annote =	{Keywords: Term modal logic, satisfiability problem, two variable fragment, decidability}
}
Document
Multimedia Exposition
Fréchet View - A Tool for Exploring Fréchet Distance Algorithms (Multimedia Exposition)

Authors: Peter Schäfer

Published in: LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019)


Abstract
The Fréchet-distance is a similarity measure for geometric shapes. Alt and Godau presented the first algorithm for computing the Fréchet-distance and introduced a key concept, the free-space diagram. Since then, numerous variants of the Fréchet-distance have been studied. We present here an interactive, graphical tool for exploring some Fréchet-distance algorithms. Given two curves, users can experiment with the free-space diagram and compute the Fréchet-distance. The Fréchet-distance can be computed for two important classes of shapes: for polygonal curves in the plane, and for simple polygonal surfaces. Finally, we demonstrate an implementation of a very recent concept, the k-Fréchet-distance.

Cite as

Peter Schäfer. Fréchet View - A Tool for Exploring Fréchet Distance Algorithms (Multimedia Exposition). In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 66:1-66:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{schafer:LIPIcs.SoCG.2019.66,
  author =	{Sch\"{a}fer, Peter},
  title =	{{Fr\'{e}chet View - A Tool for Exploring Fr\'{e}chet Distance Algorithms}},
  booktitle =	{35th International Symposium on Computational Geometry (SoCG 2019)},
  pages =	{66:1--66:5},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-104-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{129},
  editor =	{Barequet, Gill and Wang, Yusu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.66},
  URN =		{urn:nbn:de:0030-drops-104703},
  doi =		{10.4230/LIPIcs.SoCG.2019.66},
  annote =	{Keywords: Fr\'{e}chet distance, free-space diagram, polygonal curves, simple polygons}
}
Document
Approximating Maximin Share Allocations

Authors: Jugal Garg, Peter McGlaughlin, and Setareh Taki

Published in: OASIcs, Volume 69, 2nd Symposium on Simplicity in Algorithms (SOSA 2019)


Abstract
We study the problem of fair allocation of M indivisible items among N agents using the popular notion of maximin share as our measure of fairness. The maximin share of an agent is the largest value she can guarantee herself if she is allowed to choose a partition of the items into N bundles (one for each agent), on the condition that she receives her least preferred bundle. A maximin share allocation provides each agent a bundle worth at least their maximin share. While it is known that such an allocation need not exist [Procaccia and Wang, 2014; Kurokawa et al., 2016], a series of work [Procaccia and Wang, 2014; David Kurokawa et al., 2018; Amanatidis et al., 2017; Barman and Krishna Murthy, 2017] provided 2/3 approximation algorithms in which each agent receives a bundle worth at least 2/3 times their maximin share. Recently, [Ghodsi et al., 2018] improved the approximation guarantee to 3/4. Prior works utilize intricate algorithms, with an exception of [Barman and Krishna Murthy, 2017] which is a simple greedy solution but relies on sophisticated analysis techniques. In this paper, we propose an alternative 2/3 maximin share approximation which offers both a simple algorithm and straightforward analysis. In contrast to other algorithms, our approach allows for a simple and intuitive understanding of why it works.

Cite as

Jugal Garg, Peter McGlaughlin, and Setareh Taki. Approximating Maximin Share Allocations. In 2nd Symposium on Simplicity in Algorithms (SOSA 2019). Open Access Series in Informatics (OASIcs), Volume 69, pp. 20:1-20:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{garg_et_al:OASIcs.SOSA.2019.20,
  author =	{Garg, Jugal and McGlaughlin, Peter and Taki, Setareh},
  title =	{{Approximating Maximin Share Allocations}},
  booktitle =	{2nd Symposium on Simplicity in Algorithms (SOSA 2019)},
  pages =	{20:1--20:11},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-099-6},
  ISSN =	{2190-6807},
  year =	{2019},
  volume =	{69},
  editor =	{Fineman, Jeremy T. and Mitzenmacher, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.SOSA.2019.20},
  URN =		{urn:nbn:de:0030-drops-100465},
  doi =		{10.4230/OASIcs.SOSA.2019.20},
  annote =	{Keywords: Fair division, Maximin share, Approximation algorithm}
}
Document
Towards Strong Normalization for Dependent Object Types (DOT)

Authors: Fei Wang and Tiark Rompf

Published in: LIPIcs, Volume 74, 31st European Conference on Object-Oriented Programming (ECOOP 2017)


Abstract
The Dependent Object Types (DOT) family of calculi has been proposed as a new theoretic foundation for Scala and similar languages, unifying functional programming, object oriented programming and ML-style module systems. Following the recent type soundness proof for DOT, the present paper aims to establish stronger meta-theoretic properties. The main result is a fully mechanized proof of strong normalization for D_<:, a variant of DOT that excludes recursive functions and recursive types. We further discuss techniques and challenges for adding recursive types while maintaining strong normalization, and demonstrate that certain variants of recursive self types can be integrated successfully.

Cite as

Fei Wang and Tiark Rompf. Towards Strong Normalization for Dependent Object Types (DOT). In 31st European Conference on Object-Oriented Programming (ECOOP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 74, pp. 27:1-27:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)


Copy BibTex To Clipboard

@InProceedings{wang_et_al:LIPIcs.ECOOP.2017.27,
  author =	{Wang, Fei and Rompf, Tiark},
  title =	{{Towards Strong Normalization for Dependent Object Types (DOT)}},
  booktitle =	{31st European Conference on Object-Oriented Programming (ECOOP 2017)},
  pages =	{27:1--27:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-035-4},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{74},
  editor =	{M\"{u}ller, Peter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2017.27},
  URN =		{urn:nbn:de:0030-drops-72763},
  doi =		{10.4230/LIPIcs.ECOOP.2017.27},
  annote =	{Keywords: Scala, DOT, strong normalization, logical relations, recursive types}
}
Document
Minimizing the overheads of dependent {AND}-parallelism

Authors: Peter Wang and Zoltan Somogyi

Published in: LIPIcs, Volume 11, Technical Communications of the 27th International Conference on Logic Programming (ICLP'11) (2011)


Abstract
Parallel implementations of programming languages need to control synchronization overheads. Synchronization is essential for ensuring the correctness of parallel code, yet it adds overheads that aren't present in sequential programs. This is an important problem for parallel logic programming systems, because almost every action in such programs requires accessing variables, and the traditional approach of adding synchronization code to all such accesses is so prohibitively expensive that a parallel version of the program may run more slowly on four processors than a sequential version would run on one processor. We present a program transformation for implementing dependent AND-parallelism in logic programming languages that uses mode information to add synchronization code only to the variable accesses that actually need it.

Cite as

Peter Wang and Zoltan Somogyi. Minimizing the overheads of dependent {AND}-parallelism. In Technical Communications of the 27th International Conference on Logic Programming (ICLP'11). Leibniz International Proceedings in Informatics (LIPIcs), Volume 11, pp. 128-138, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)


Copy BibTex To Clipboard

@InProceedings{wang_et_al:LIPIcs.ICLP.2011.128,
  author =	{Wang, Peter and Somogyi, Zoltan},
  title =	{{Minimizing the overheads of dependent \{AND\}-parallelism}},
  booktitle =	{Technical Communications of the 27th International Conference on Logic Programming (ICLP'11)},
  pages =	{128--138},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-31-6},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{11},
  editor =	{Gallagher, John P. and Gelfond, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICLP.2011.128},
  URN =		{urn:nbn:de:0030-drops-31667},
  doi =		{10.4230/LIPIcs.ICLP.2011.128},
  annote =	{Keywords: synchronization, program transformation}
}
Document
Discovery of Sensor Network Layout using Connectivity Information

Authors: Jie Gao, Sol Lederer, and Yue Wang

Published in: Dagstuhl Seminar Proceedings, Volume 7151, Geometry in Sensor Networks (2007)


Abstract
We propose a distributed algorithm to discover and recover the layout of a large sensor network having a complex shape. As sensor network deployments grow large in size and become non-uniform, localization algorithms suffer from ``flip'' ambiguities---where a part of the network folds on top of another while keeping all edge length measurements preserved. We explore the high-order topological information in a sensor field to prevent incorrect flips and accurately recover the shape of the sensor network. We select landmarks on network boundaries with sufficient density, construct the landmark Voronoi diagram and its dual combinatorial Delaunay complex on these landmarks. The key insight is that when the landmarks are dense enough to capture the local geometric complexity, the combinatorial Delaunay complex is globally rigid and has a unique realization in the plane. An embedding by simply gluing the Delaunay triangles properly derives a faithful network layout, which consequently leads to a practical and sufficiently accurate localization algorithm. We prove the global rigidity of the combinatorial Delaunay complex in the case of a continuous geometric region. Simulation results on discrete networks show surprisingly good results, while multi-dimensional scaling and rubberband representation perform poorly or not at all in recovering the network layout. This is joint work with Sol Lederer and Yue Wang.

Cite as

Jie Gao, Sol Lederer, and Yue Wang. Discovery of Sensor Network Layout using Connectivity Information. In Geometry in Sensor Networks. Dagstuhl Seminar Proceedings, Volume 7151, pp. 1-14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)


Copy BibTex To Clipboard

@InProceedings{gao_et_al:DagSemProc.07151.2,
  author =	{Gao, Jie and Lederer, Sol and Wang, Yue},
  title =	{{Discovery of Sensor Network Layout using Connectivity Information}},
  booktitle =	{Geometry in Sensor Networks},
  pages =	{1--14},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{7151},
  editor =	{Subhash Suri and Roger Wattenhofer and Peter Widmayer},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.07151.2},
  URN =		{urn:nbn:de:0030-drops-11149},
  doi =		{10.4230/DagSemProc.07151.2},
  annote =	{Keywords: Sensor Networks, Localization, Delaunay complex, Rigidity}
}
  • Refine by Author
  • 1 Abejirinde, Ibukun-Oluwa O.
  • 1 Afolabi, Bosede B.
  • 1 Banke-Thomas, Aduragbemi
  • 1 Beňová, Lenka
  • 1 Bian, Xiaoning
  • Show More...

  • Refine by Classification
  • 1 Computer systems organization → Quantum computing
  • 1 Information systems → Geographic information systems
  • 1 Theory of computation → Computational geometry
  • 1 Theory of computation → Distributed algorithms
  • 1 Theory of computation → Distributed computing models
  • Show More...

  • Refine by Keyword
  • 1 Accessibility
  • 1 Approximation algorithm
  • 1 Big Data
  • 1 Clifford hierarchy
  • 1 DOT
  • Show More...

  • Refine by Type
  • 11 document

  • Refine by Publication Year
  • 4 2019
  • 2 2023
  • 1 2007
  • 1 2011
  • 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