3 Search Results for "Jones, Daniel"

Document
DOI: 10.4230/LIPIcs.CCC.2023.30
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-dev.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
DOI: 10.4230/OASIcs.ICCSW.2012.69
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-dev.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
DOI: 10.4230/DagSemProc.09291.28
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-dev.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 Berry, Rodney
  • 1 Bown, Oliver
  • 1 Hajnal, Jo
  • 1 Jantsch, Martin
  • Show More...

  • Refine by Classification
  • 1 Mathematics of computing → Combinatorial optimization
  • 1 Theory of computation → Pseudorandomness and derandomization
  • 1 Theory of computation → Semidefinite programming

  • Refine by Keyword
  • 1 Cardiac
  • 1 Computational creativity
  • 1 MRI
  • 1 Paley graph
  • 1 Registration
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 1 2009
  • 1 2012
  • 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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact