5 Search Results for "Jones, Daniel"


Document
FREIGHT: Fast Streaming Hypergraph Partitioning

Authors: Kamal Eyubov, Marcelo Fonseca Faraj, and Christian Schulz

Published in: LIPIcs, Volume 265, 21st International Symposium on Experimental Algorithms (SEA 2023)


Abstract
Partitioning the vertices of a (hyper)graph into k roughly balanced blocks such that few (hyper)edges run between blocks is a key problem for large-scale distributed processing. A current trend for partitioning huge (hyper)graphs using low computational resources are streaming algorithms. In this work, we propose FREIGHT: a Fast stREamInG Hypergraph parTitioning algorithm which is an adaptation of the widely-known graph-based algorithm Fennel. By using an efficient data structure, we make the overall running of FREIGHT linearly dependent on the pin-count of the hypergraph and the memory consumption linearly dependent on the numbers of nets and blocks. The results of our extensive experimentation showcase the promising performance of FREIGHT as a highly efficient and effective solution for streaming hypergraph partitioning. Our algorithm demonstrates competitive running time with the Hashing algorithm, with a difference of a maximum factor of four observed on three fourths of the instances. Significantly, our findings highlight the superiority of FREIGHT over all existing (buffered) streaming algorithms and even the in-memory algorithm HYPE, with respect to both cut-net and connectivity measures. This indicates that our proposed algorithm is a promising hypergraph partitioning tool to tackle the challenge posed by large-scale and dynamic data processing.

Cite as

Kamal Eyubov, Marcelo Fonseca Faraj, and Christian Schulz. FREIGHT: Fast Streaming Hypergraph Partitioning. In 21st International Symposium on Experimental Algorithms (SEA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 265, pp. 15:1-15:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{eyubov_et_al:LIPIcs.SEA.2023.15,
  author =	{Eyubov, Kamal and Fonseca Faraj, Marcelo and Schulz, Christian},
  title =	{{FREIGHT: Fast Streaming Hypergraph Partitioning}},
  booktitle =	{21st International Symposium on Experimental Algorithms (SEA 2023)},
  pages =	{15:1--15:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-279-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{265},
  editor =	{Georgiadis, Loukas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2023.15},
  URN =		{urn:nbn:de:0030-drops-183657},
  doi =		{10.4230/LIPIcs.SEA.2023.15},
  annote =	{Keywords: Hypergraph partitioning, graph partitioning, edge partitioning, streaming}
}
Document
A Degree 4 Sum-Of-Squares Lower Bound for the Clique Number of the Paley Graph

Authors: Dmitriy Kunisky and Xifan Yu

Published in: LIPIcs, Volume 264, 38th Computational Complexity Conference (CCC 2023)


Abstract
We prove that the degree 4 sum-of-squares (SOS) relaxation of the clique number of the Paley graph on a prime number p of vertices has value at least Ω(p^{1/3}). This is in contrast to the widely believed conjecture that the actual clique number of the Paley graph is O(polylog(p)). Our result may be viewed as a derandomization of that of Deshpande and Montanari (2015), who showed the same lower bound (up to polylog(p) terms) with high probability for the Erdős-Rényi random graph on p vertices, whose clique number is with high probability O(log(p)). We also show that our lower bound is optimal for the Feige-Krauthgamer construction of pseudomoments, derandomizing an argument of Kelner. Finally, we present numerical experiments indicating that the value of the degree 4 SOS relaxation of the Paley graph may scale as O(p^{1/2 - ε}) for some ε > 0, and give a matrix norm calculation indicating that the pseudocalibration construction for SOS lower bounds for random graphs will not immediately transfer to the Paley graph. Taken together, our results suggest that degree 4 SOS may break the "√p barrier" for upper bounds on the clique number of Paley graphs, but prove that it can at best improve the exponent from 1/2 to 1/3.

Cite as

Dmitriy Kunisky and Xifan Yu. A Degree 4 Sum-Of-Squares Lower Bound for the Clique Number of the Paley Graph. In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 30:1-30:25, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{kunisky_et_al:LIPIcs.CCC.2023.30,
  author =	{Kunisky, Dmitriy and Yu, Xifan},
  title =	{{A Degree 4 Sum-Of-Squares Lower Bound for the Clique Number of the Paley Graph}},
  booktitle =	{38th Computational Complexity Conference (CCC 2023)},
  pages =	{30:1--30:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-282-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{264},
  editor =	{Ta-Shma, Amnon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2023.30},
  URN =		{urn:nbn:de:0030-drops-183008},
  doi =		{10.4230/LIPIcs.CCC.2023.30},
  annote =	{Keywords: convex optimization, sum of squares, Paley graph, derandomization}
}
Document
Characterizing Data Dependence Constraints for Dynamic Reliability Using n-Queens Attack Domains

Authors: Eric W. D. Rozier, Kristin Y. Rozier, and Ulya Bayram

Published in: LITES, Volume 4, Issue 1 (2017). Leibniz Transactions on Embedded Systems, Volume 4, Issue 1


Abstract
As data centers attempt to cope with the exponential growth of data, new techniques for intelligent, software-defined data centers (SDDC) are being developed to confront the scale and pace of changing resources and requirements.  For cost-constrained environments, like those increasingly present in scientific research labs, SDDCs also may provide better reliability and performability with no additional hardware through the use of dynamic syndrome allocation. To do so, the middleware layers of SDDCs must be able to calculate and account for complex dependence relationships to determine an optimal data layout.  This challenge is exacerbated by the growth of constraints on the dependence problem when available resources are both large (due to a higher number of syndromes that can be stored) and small (due to the lack of available space for syndrome allocation). We present a quantitative method for characterizing these challenges using an analysis of attack domains for high-dimension variants of the $n$-queens problem that enables performable solutions via the SMT solver Z3. We demonstrate correctness of our technique, and provide experimental evidence of its efficacy; our implementation is publicly available.

Cite as

Eric W. D. Rozier, Kristin Y. Rozier, and Ulya Bayram. Characterizing Data Dependence Constraints for Dynamic Reliability Using n-Queens Attack Domains. In LITES, Volume 4, Issue 1 (2017). Leibniz Transactions on Embedded Systems, Volume 4, Issue 1, pp. 05:1-05:26, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)


Copy BibTex To Clipboard

@Article{rozier_et_al:LITES-v004-i001-a005,
  author =	{Rozier, Eric W. D. and Rozier, Kristin Y. and Bayram, Ulya},
  title =	{{Characterizing Data Dependence Constraints for Dynamic Reliability Using n-Queens Attack Domains}},
  booktitle =	{LITES, Volume 4, Issue 1 (2017)},
  pages =	{05:1--05:26},
  journal =	{Leibniz Transactions on Embedded Systems},
  ISSN =	{2199-2002},
  year =	{2017},
  volume =	{4},
  number =	{1},
  editor =	{Rozier, Eric W. D. and Rozier, Kristin Y. and Bayram, Ulya},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LITES-v004-i001-a005},
  doi =		{10.4230/LITES-v004-i001-a005},
  annote =	{Keywords: SMT, Data dependence, n-queens}
}
Document
4D Cardiac Volume Reconstruction from Free-Breathing 2D Real-Time Image Acquisitions using Iterative Motion Correction

Authors: Martin Jantsch, Daniel Rueckert, and Jo Hajnal

Published in: OASIcs, Volume 28, 2012 Imperial College Computing Student Workshop


Abstract
For diagnosis, treatment and study of various cardiac diseases directly affecting the functionality and morphology of the heart, physicians rely more and more on MR imaging techniques. MRI has good tissue contrast and can achieve high spatial and temporal resolutions. However it requires a relatively long time to obtain enough data to reconstruct useful images. Additionally, when imaging the heart, the occurring motions - breathing and heart beat - have to be taken into account. While the cardiac motion still has to be correctly seen to asses functionality, the respiratory motion has to be removed to avoid serious motion artefacts. We present initial results for a reconstruction pipeline that takes multiple stacks of 2D slices, calculates the occurring deformations for both cardiac and respiratory motions and reconstructs a coherent 4D volume of the beating heart. The 2D slices are acquired during free-breathing over the whole respiratory cycle, using a fast real-time technique. For motion estimation two different transformation models were used. A cyclic 4D B-spline free-form deformation model for the cardiac motion and a 1D B-spline affine model for the respiratory motion. Both transformations and the common reference frame needed for the registration are optimized in an interleaved, iterative scheme.

Cite as

Martin Jantsch, Daniel Rueckert, and Jo Hajnal. 4D Cardiac Volume Reconstruction from Free-Breathing 2D Real-Time Image Acquisitions using Iterative Motion Correction. In 2012 Imperial College Computing Student Workshop. Open Access Series in Informatics (OASIcs), Volume 28, pp. 69-74, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2012)


Copy BibTex To Clipboard

@InProceedings{jantsch_et_al:OASIcs.ICCSW.2012.69,
  author =	{Jantsch, Martin and Rueckert, Daniel and Hajnal, Jo},
  title =	{{4D Cardiac Volume Reconstruction from Free-Breathing 2D Real-Time Image Acquisitions using Iterative Motion Correction}},
  booktitle =	{2012 Imperial College Computing Student Workshop},
  pages =	{69--74},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-48-4},
  ISSN =	{2190-6807},
  year =	{2012},
  volume =	{28},
  editor =	{Jones, Andrew V.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ICCSW.2012.69},
  URN =		{urn:nbn:de:0030-drops-37676},
  doi =		{10.4230/OASIcs.ICCSW.2012.69},
  annote =	{Keywords: MRI, Cardiac, Registration}
}
Document
Stimulating creative flow through computational feedback

Authors: Daniel Jones, Oliver Bown, Jon McCormack, Francois Pachet, Michael Young, Rodney Berry, Iris Asaf, and Benjamin Porter

Published in: Dagstuhl Seminar Proceedings, Volume 9291, Computational Creativity: An Interdisciplinary Approach (2009)


Abstract
This report summarises the discussion and experimental work produced by the authors at the 2009 symposium Computational Creativity: An Interdisciplinary Approach, Dagstuhl Leibniz-Zentrum für Informatik. It outlines the motivation for using computational techniques to stimulate human creativity, briefly summarising its historical context and predecessors, and describes two software studies produced by the group as base-line exemplars of these ideas.

Cite as

Daniel Jones, Oliver Bown, Jon McCormack, Francois Pachet, Michael Young, Rodney Berry, Iris Asaf, and Benjamin Porter. Stimulating creative flow through computational feedback. In Computational Creativity: An Interdisciplinary Approach. Dagstuhl Seminar Proceedings, Volume 9291, pp. 1-10, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2009)


Copy BibTex To Clipboard

@InProceedings{jones_et_al:DagSemProc.09291.28,
  author =	{Jones, Daniel and Bown, Oliver and McCormack, Jon and Pachet, Francois and Young, Michael and Berry, Rodney and Asaf, Iris and Porter, Benjamin},
  title =	{{Stimulating creative flow through computational feedback}},
  booktitle =	{Computational Creativity: An Interdisciplinary Approach},
  pages =	{1--10},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{9291},
  editor =	{Margaret Boden and Mark D'Inverno and Jon McCormack},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.09291.28},
  URN =		{urn:nbn:de:0030-drops-22232},
  doi =		{10.4230/DagSemProc.09291.28},
  annote =	{Keywords: Computational creativity}
}
  • Refine by Author
  • 1 Asaf, Iris
  • 1 Bayram, Ulya
  • 1 Berry, Rodney
  • 1 Bown, Oliver
  • 1 Eyubov, Kamal
  • Show More...

  • Refine by Classification
  • 1 Computer systems organization → Embedded and cyber-physical systems
  • 1 Hardware → Theorem proving and SAT solving
  • 1 Information systems → Data centers
  • 1 Mathematics of computing → Combinatorial optimization
  • 1 Theory of computation → Graph algorithms analysis
  • Show More...

  • Refine by Keyword
  • 1 Cardiac
  • 1 Computational creativity
  • 1 Data dependence
  • 1 Hypergraph partitioning
  • 1 MRI
  • Show More...

  • Refine by Type
  • 5 document

  • Refine by Publication Year
  • 2 2023
  • 1 2009
  • 1 2012
  • 1 2017

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