6 Search Results for "Joy, Kenneth I."

Document
DOI: 10.4230/LIPIcs.ITCS.2025.89
Optimal Communication Complexity of Chained Index

Authors: Janani Sundaresan

Published in: LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)

Abstract
We study the chain communication problem introduced by Cormode et al. [ICALP 2019]. For k ≥ 1, in the chain_{n,k} problem, there are k string and index pairs (X_i, σ_i) for i ∈ [k] such that the value at position σ_i in string X_i is the same bit for all k pairs. The input is shared between k+1 players as follows. Player 1 has the first string X₁ ∈ {0,1}ⁿ, player 2 has the first index σ₁ ∈ [n] and the second string X₂ ∈ {0,1}ⁿ, player 3 has the second index σ₂ ∈ [n] along with the third string X₃ ∈ {0,1}ⁿ, and so on. Player k+1 has the last index σ_k ∈ [n]. The communication is one way from each player to the next, starting from player 1 to player 2, then from player 2 to player 3 and so on. Player k+1, after receiving the message from player k, has to output a single bit which is the value at position σ_i in X_i for any i ∈ [k]. It is a generalization of the well-studied index problem, which is equivalent to chain_{n, 2}. Cormode et al. proved that the chain_{n,k} problem requires Ω(n/k²) communication, and they used it to prove streaming lower bounds for the approximation of maximum independent sets. Subsequently, Feldman et al. [STOC 2020] used it to prove lower bounds for streaming submodular maximization. However, it is not known whether the Ω(n/k²) lower bound used in these works is optimal for the problem, and in fact, it was conjectured by Cormode et al. that Ω(n) bits are necessary. We prove the optimal lower bound of Ω(n) for chain_{n,k} when k = o(n/log n) as our main result. This settles the open conjecture of Cormode et al., barring the range of k = Ω(n /log n). The main technique is a reduction to a non-standard index problem where the input to the players is such that the answer is biased away from uniform. This biased version of index is analyzed using tools from information theory. As a corollary, we get an improved lower bound for approximation of maximum independent set in vertex arrival streams via a reduction from chain directly.
Cite as

Janani Sundaresan. Optimal Communication Complexity of Chained Index. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 89:1-89:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{sundaresan:LIPIcs.ITCS.2025.89,
  author =	{Sundaresan, Janani},
  title =	{{Optimal Communication Complexity of Chained Index}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{89:1--89:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-361-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{325},
  editor =	{Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.89},
  URN =		{urn:nbn:de:0030-drops-227172},
  doi =		{10.4230/LIPIcs.ITCS.2025.89},
  annote =	{Keywords: communication complexity, index communciation problem}
}
Document
DOI: 10.4230/OASIcs.VLUDS.2011.71
Feature-based Visualization of Dense Integral Line Data

Authors: Simon Schröder, Harald Obermaier, Christoph Garth, and Kenneth I. Joy

Published in: OASIcs, Volume 27, Visualization of Large and Unstructured Data Sets: Applications in Geospatial Planning, Modeling and Engineering - Proceedings of IRTG 1131 Workshop 2011

Abstract
Feature-based visualization of flow fields has proven as an effective tool for flow analysis. While most flow visualization techniques operate on vector field data, our visualization techniques make use of a different simulation output: Particle Tracers. Our approach solely relies on integral lines that can be easily obtained from most simulation software. The task is the visualization of dense integral line data. We combine existing methods for streamline visualization, i.e. illumination, transparency, and halos, and add ambient occlusion for lines. But, this only solves one part of the problem: because of the high density of lines, visualization has to fight with occlusion, high frequency noise, and overlaps. As a solution we propose non-automated choices of transfer functions on curve properties that help highlighting important flow features like vortices or turbulent areas. These curve properties resemble some of the original flow properties. With the new combination of existing line drawing methods and the addition of ambient occlusion we improve the visualization of lines by adding better shape and depth cues. The intelligent use of transfer functions on curve properties reduces visual clutter and helps focusing on important features while still retaining context, as demonstrated in the examples given in this work.
Cite as

Simon Schröder, Harald Obermaier, Christoph Garth, and Kenneth I. Joy. Feature-based Visualization of Dense Integral Line Data. In Visualization of Large and Unstructured Data Sets: Applications in Geospatial Planning, Modeling and Engineering - Proceedings of IRTG 1131 Workshop 2011. Open Access Series in Informatics (OASIcs), Volume 27, pp. 71-87, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{schroder_et_al:OASIcs.VLUDS.2011.71,
  author =	{Schr\"{o}der, Simon and Obermaier, Harald and Garth, Christoph and Joy, Kenneth I.},
  title =	{{Feature-based Visualization of Dense Integral Line Data}},
  booktitle =	{Visualization of Large and Unstructured Data Sets: Applications in Geospatial Planning, Modeling and Engineering - Proceedings of IRTG 1131 Workshop 2011},
  pages =	{71--87},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-46-0},
  ISSN =	{2190-6807},
  year =	{2012},
  volume =	{27},
  editor =	{Garth, Christoph and Middel, Ariane and Hagen, Hans},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.VLUDS.2011.71},
  URN =		{urn:nbn:de:0030-drops-37424},
  doi =		{10.4230/OASIcs.VLUDS.2011.71},
  annote =	{Keywords: flow simulation, feature-based visualization, dense lines, ambient occlusion}
}
Document
DOI: 10.4230/DFU.Vol2.SciViz.2011.59
Comparative Visualization Using Cross-Mesh Field Evaluations and Derived Quantities

Authors: Hank Childs, Sean Ahern, Jeremy Meredith, Mark Miller, and Kenneth I. Joy

Published in: Dagstuhl Follow-Ups, Volume 2, Scientific Visualization: Interactions, Features, Metaphors (2011)

Abstract
We present a data-level comparative visualization system that utilizes two key pieces of technology: (1) cross-mesh field evaluation - algorithms to evaluate a field from one mesh onto another - and (2) a highly flexible system for creating new derived quantities. In contrast to previous comparative visualization efforts, which focused on "A-B" comparisons, our system is able to compare many related simulations in a single analysis. Types of possible novel comparisons include comparisons of ensembles of data generated through parameter studies, or comparisons of time-varying data. All portions of the system have been parallelized and our results are applicable to petascale data sets.
Cite as

Hank Childs, Sean Ahern, Jeremy Meredith, Mark Miller, and Kenneth I. Joy. Comparative Visualization Using Cross-Mesh Field Evaluations and Derived Quantities. In Scientific Visualization: Interactions, Features, Metaphors. Dagstuhl Follow-Ups, Volume 2, pp. 59-72, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InCollection{childs_et_al:DFU.Vol2.SciViz.2011.59,
  author =	{Childs, Hank and Ahern, Sean and Meredith, Jeremy and Miller, Mark and Joy, Kenneth I.},
  title =	{{Comparative Visualization Using Cross-Mesh Field Evaluations and Derived Quantities}},
  booktitle =	{Scientific Visualization: Interactions, Features, Metaphors},
  pages =	{59--72},
  series =	{Dagstuhl Follow-Ups},
  ISBN =	{978-3-939897-26-2},
  ISSN =	{1868-8977},
  year =	{2011},
  volume =	{2},
  editor =	{Hagen, Hans},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DFU.Vol2.SciViz.2011.59},
  URN =		{urn:nbn:de:0030-drops-32870},
  doi =		{10.4230/DFU.Vol2.SciViz.2011.59},
  annote =	{Keywords: Comparative Visualization, Cross-Mesh Field Evaluation, Derived Quantity}
}
Document
DOI: 10.4230/DFU.SciViz.2010.336
Streaming Aerial Video Textures

Authors: Christopher S. Co, Mark A. Duchaineau, and Kenneth I. Joy

Published in: Dagstuhl Follow-Ups, Volume 1, Scientific Visualization: Advanced Concepts (2010)

Abstract
We present a streaming compression algorithm for huge time-varying aerial imagery. New airborne optical sensors are capable of collecting billion-pixel images at multiple frames per second. These images must be transmitted through a low-bandwidth pipe requiring aggressive compression techniques. We achieve such compression by treating foreground portions of the imagery separately from background portions. Foreground information consists of moving objects, which form a tiny fraction of the total pixels. Background areas are compressed effectively over time using streaming wavelet analysis to compute a compact video texture map that represents several frames of raw input images. This map can be rendered efficiently using an algorithm amenable to GPU implementation. The core algorithmic contributions of this work are methods for fast, low-memory streaming wavelet compression and efficient display of wavelet video textures resulting from such compression.
Cite as

Christopher S. Co, Mark A. Duchaineau, and Kenneth I. Joy. Streaming Aerial Video Textures. In Scientific Visualization: Advanced Concepts. Dagstuhl Follow-Ups, Volume 1, pp. 336-345, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InCollection{co_et_al:DFU.SciViz.2010.336,
  author =	{Co, Christopher S. and Duchaineau, Mark A. and Joy, Kenneth I.},
  title =	{{Streaming Aerial Video Textures}},
  booktitle =	{Scientific Visualization: Advanced Concepts},
  pages =	{336--345},
  series =	{Dagstuhl Follow-Ups},
  ISBN =	{978-3-939897-19-4},
  ISSN =	{1868-8977},
  year =	{2010},
  volume =	{1},
  editor =	{Hagen, Hans},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DFU.SciViz.2010.336},
  URN =		{urn:nbn:de:0030-drops-27148},
  doi =		{10.4230/DFU.SciViz.2010.336},
  annote =	{Keywords: Molecuar Dynamics, Saliency, Simulation}
}
Document
DOI: 10.4230/DagSemProc.07291.1
07291 Abstracts Collection – Scientific Visualization

Authors: David S. Ebert, Hans Hagen, Kenneth I. Joy, and Daniel A. Keim

Published in: Dagstuhl Seminar Proceedings, Volume 7291, Scientific Visualization (2008)

Abstract
From 15.07. to 20.07.07, the Dagstuhl Seminar 07291 ``Scientific Visualization'' was held in the International Conference and Research Center (IBFI),Schloss Dagstuhl. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
Cite as

David S. Ebert, Hans Hagen, Kenneth I. Joy, and Daniel A. Keim. 07291 Abstracts Collection – Scientific Visualization. In Scientific Visualization. Dagstuhl Seminar Proceedings, Volume 7291, pp. 1-18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{ebert_et_al:DagSemProc.07291.1,
  author =	{Ebert, David S. and Hagen, Hans and Joy, Kenneth I. and Keim, Daniel A.},
  title =	{{07291 Abstracts Collection – Scientific Visualization}},
  booktitle =	{Scientific Visualization},
  pages =	{1--18},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{7291},
  editor =	{David S. Ebert and Hans Hagen and Kenneth I. Joy and Daniel A. Keim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07291.1},
  URN =		{urn:nbn:de:0030-drops-14145},
  doi =		{10.4230/DagSemProc.07291.1},
  annote =	{Keywords: Markov chains, numerical methods, web information retrieval, performance evaluation, intrusion detection, aggregation-disaggregation methods, graph-oriented decomposition}
}
Document
DOI: 10.4230/DagSemProc.07291.2
07291 Summary – Scientific Visualization

Authors: David S. Ebert, Hans Hagen, Kenneth I. Joy, and Daniel A. Keim

Published in: Dagstuhl Seminar Proceedings, Volume 7291, Scientific Visualization (2008)

Abstract
Scientific visualization (SV) is concerned with the use of computer-generated images to aid the understanding, analysis and manipulation of data. Since its beginning in the early 90's, the techniques of SV have aided scientists, engineers, medical practitioners, and others in the study of a wide variety of data sets including, for example, high performance computing simulations, measured data from scanners (CAT, MR, confocal microscopy), internet traffic, and financial records. One of the important themes being nurtured under the aegis of Scientific Visualization is the utilization of the broad bandwidth of the human sensory system in steering and interpreting complex processes and simulations involving voluminous data sets across diverse scientific disciplines. Since vision dominates our sensory input, strong efforts have been made to bring the mathematical abstraction and modeling to our eyes through the mediation of computer graphics. This interplay between various application areas and their specific problem solving visualization techniques was emphasized in the proposed seminar.
Cite as

David S. Ebert, Hans Hagen, Kenneth I. Joy, and Daniel A. Keim. 07291 Summary – Scientific Visualization. In Scientific Visualization. Dagstuhl Seminar Proceedings, Volume 7291, pp. 1-2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{ebert_et_al:DagSemProc.07291.2,
  author =	{Ebert, David S. and Hagen, Hans and Joy, Kenneth I. and Keim, Daniel A.},
  title =	{{07291 Summary – Scientific Visualization}},
  booktitle =	{Scientific Visualization},
  pages =	{1--2},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{7291},
  editor =	{David S. Ebert and Hans Hagen and Kenneth I. Joy and Daniel A. Keim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07291.2},
  URN =		{urn:nbn:de:0030-drops-14132},
  doi =		{10.4230/DagSemProc.07291.2},
  annote =	{Keywords: Markov chains, numerical methods, web information retrieval, performance evaluation, intrusion detection, aggregation-disaggregation methods graph-oriented decomposition}
}
  • Refine by Type
  • 6 Document/PDF
  • 1 Document/HTML

  • Refine by Publication Year
  • 1 2025
  • 1 2012
  • 1 2011
  • 1 2010
  • 2 2008

  • Refine by Author
  • 5 Joy, Kenneth I.
  • 2 Ebert, David S.
  • 2 Hagen, Hans
  • 2 Keim, Daniel A.
  • 1 Ahern, Sean
  • Show More...

  • Refine by Series/Journal
  • 1 LIPIcs
  • 1 OASIcs
  • 2 DFU
  • 2 DagSemProc

  • Refine by Classification
  • 1 Theory of computation → Communication complexity

  • Refine by Keyword
  • 2 Markov chains
  • 2 intrusion detection
  • 2 numerical methods
  • 2 performance evaluation
  • 2 web information retrieval
  • Show More...

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