7 Search Results for "Tucker-Foltz, Jamie"

Document
DOI: 10.4230/LIPIcs.SoCG.2025.58
Tracking the Persistence of Harmonic Chains: Barcode and Stability

Authors: Tao Hou, Salman Parsa, and Bei Wang

Published in: LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025)

Abstract
The persistence barcode is a topological descriptor of data that plays a fundamental role in topological data analysis. Given a filtration of data, the persistence barcode tracks the evolution of its homology groups. In this paper, we introduce a new type of barcode, called the harmonic chain barcode, which tracks the evolution of harmonic chains. In addition, we show that the harmonic chain barcode is stable. Given a filtration of a simplicial complex of size m, we present an algorithm to compute its harmonic chain barcode in O(m³) time. Consequently, the harmonic chain barcode can enrich the family of topological descriptors in applications where a persistence barcode is applicable, such as feature vectorization and machine learning.
Cite as

Tao Hou, Salman Parsa, and Bei Wang. Tracking the Persistence of Harmonic Chains: Barcode and Stability. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 58:1-58:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{hou_et_al:LIPIcs.SoCG.2025.58,
  author =	{Hou, Tao and Parsa, Salman and Wang, Bei},
  title =	{{Tracking the Persistence of Harmonic Chains: Barcode and Stability}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{58:1--58:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.58},
  URN =		{urn:nbn:de:0030-drops-232100},
  doi =		{10.4230/LIPIcs.SoCG.2025.58},
  annote =	{Keywords: Persistent homology, harmonic chains, topological data analysis}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2025.74
The Point-Boundary Art Gallery Problem Is ∃ℝ-Hard

Authors: Jack Stade

Published in: LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025)

Abstract
We resolve the complexity of the point-boundary variant of the art gallery problem, showing that it is ∃ℝ-complete, meaning that it is equivalent under polynomial time reductions to deciding whether a system of polynomial equations has a real solution. The art gallery problem asks whether there is a configuration of guards that together can see every point inside of an art gallery modeled by a simple polygon. The original version of this problem (which we call the point-point variant) was shown to be ∃ℝ-hard [Abrahamsen, Adamaszek, and Miltzow, JACM 2021], but the complexity of the variant where guards only need to guard the walls of the art gallery was left as an open problem. We show that this variant is also ∃ℝ-hard. Our techniques can also be used to greatly simplify the proof of ∃ℝ-hardness of the point-point art gallery problem. The gadgets in previous work could only be constructed by using a computer to find complicated rational coordinates with specific algebraic properties. All of our gadgets can be constructed by hand and can be verified with simple geometric arguments.
Cite as

Jack Stade. The Point-Boundary Art Gallery Problem Is ∃ℝ-Hard. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 74:1-74:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{stade:LIPIcs.SoCG.2025.74,
  author =	{Stade, Jack},
  title =	{{The Point-Boundary Art Gallery Problem Is \exists\mathbb{R}-Hard}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{74:1--74:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.74},
  URN =		{urn:nbn:de:0030-drops-232269},
  doi =		{10.4230/LIPIcs.SoCG.2025.74},
  annote =	{Keywords: Art Gallery Problem, Complexity, ETR, Polygon}
}
Document
DOI: 10.4230/LIPIcs.FORC.2025.20
Group Fairness and Multi-Criteria Optimization in School Assignment

Authors: Santhini K. A., Kamesh Munagala, Meghana Nasre, and Govind S. Sankar

Published in: LIPIcs, Volume 329, 6th Symposium on Foundations of Responsible Computing (FORC 2025)

Abstract
We consider the problem of assigning students to schools when students have different utilities for schools and schools have limited capacities. The students belong to demographic groups, and fairness over these groups is captured either by concave objectives, or additional constraints on the utility of the groups. We present approximation algorithms for this assignment problem with group fairness via convex program rounding. These algorithms achieve various trade-offs between capacity violation and running time. We also show that our techniques easily extend to the setting where there are arbitrary constraints on the feasible assignment, capturing multi-criteria optimization. We present simulation results that demonstrate that the rounding methods are practical even on large problem instances, with the empirical capacity violation being much better than the theoretical bounds.
Cite as

Santhini K. A., Kamesh Munagala, Meghana Nasre, and Govind S. Sankar. Group Fairness and Multi-Criteria Optimization in School Assignment. In 6th Symposium on Foundations of Responsible Computing (FORC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 329, pp. 20:1-20:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{k.a._et_al:LIPIcs.FORC.2025.20,
  author =	{K. A., Santhini and Munagala, Kamesh and Nasre, Meghana and S. Sankar, Govind},
  title =	{{Group Fairness and Multi-Criteria Optimization in School Assignment}},
  booktitle =	{6th Symposium on Foundations of Responsible Computing (FORC 2025)},
  pages =	{20:1--20:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-367-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{329},
  editor =	{Bun, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FORC.2025.20},
  URN =		{urn:nbn:de:0030-drops-231471},
  doi =		{10.4230/LIPIcs.FORC.2025.20},
  annote =	{Keywords: School Assignment, Approximation Algorithms, Group Fairness}
}
Document
DOI: 10.4230/LIPIcs.CSL.2025.14
Finite Variable Counting Logics with Restricted Requantification

Authors: Simon Raßmann, Georg Schindling, and Pascal Schweitzer

Published in: LIPIcs, Volume 326, 33rd EACSL Annual Conference on Computer Science Logic (CSL 2025)

Abstract
Counting logics with a bounded number of variables form one of the central concepts in descriptive complexity theory. Although they restrict the number of variables that a formula can contain, the variables can be nested within scopes of quantified occurrences of themselves. In other words, the variables can be requantified. We study the fragments obtained from counting logics by restricting requantification for some but not necessarily all the variables. Similar to the logics without limitation on requantification, we develop tools to investigate the restricted variants. Specifically, we introduce a bijective pebble game in which certain pebbles can only be placed once and for all, and a corresponding two-parametric family of Weisfeiler-Leman algorithms. We show close correspondences between the three concepts. By using a suitable cops-and-robber game and adaptations of the Cai-Fürer-Immerman construction, we completely clarify the relative expressive power of the new logics. We show that the restriction of requantification has beneficial algorithmic implications in terms of graph identification. Indeed, we argue that with regard to space complexity, non-requantifiable variables only incur an additive polynomial factor when testing for equivalence. In contrast, for all we know, requantifiable variables incur a multiplicative linear factor. Finally, we observe that graphs of bounded tree-depth and 3-connected planar graphs can be identified using no, respectively, only a very limited number of requantifiable variables.
Cite as

Simon Raßmann, Georg Schindling, and Pascal Schweitzer. Finite Variable Counting Logics with Restricted Requantification. In 33rd EACSL Annual Conference on Computer Science Logic (CSL 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 326, pp. 14:1-14:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{ramann_et_al:LIPIcs.CSL.2025.14,
  author =	{Ra{\ss}mann, Simon and Schindling, Georg and Schweitzer, Pascal},
  title =	{{Finite Variable Counting Logics with Restricted Requantification}},
  booktitle =	{33rd EACSL Annual Conference on Computer Science Logic (CSL 2025)},
  pages =	{14:1--14:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-362-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{326},
  editor =	{Endrullis, J\"{o}rg and Schmitz, Sylvain},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2025.14},
  URN =		{urn:nbn:de:0030-drops-227716},
  doi =		{10.4230/LIPIcs.CSL.2025.14},
  annote =	{Keywords: Requantification, Finite variable counting logics, Weisfeiler-Leman algorithm}
}
Document
DOI: 10.4230/LIPIcs.CSL.2025.16
Undefinability of Approximation of 2-To-2 Games

Authors: Anuj Dawar and Bálint Molnár

Published in: LIPIcs, Volume 326, 33rd EACSL Annual Conference on Computer Science Logic (CSL 2025)

Abstract
Recent work by Atserias and Dawar [Albert Atserias and Anuj Dawar, 2019] and Tucker-Foltz [Jamie Tucker-Foltz, 2024] has established undefinability results in fixed-point logic with counting (FPC) corresponding to many classical complexity results from the hardness of approximation. In this line of work, NP-hardness results are turned into unconditional FPC undefinability results. We extend this work by showing the FPC undefinability of any constant factor approximation of weighted 2-to-2 games, based on the NP-hardness results of Khot, Minzer and Safra. Our result shows that the completely satisfiable 2-to-2 games are not FPC-separable from those that are not ε-satisfiable, for arbitrarily small ε. The perfect completeness of our inseparability is an improvement on the complexity result, as the NP-hardness of such a separation is still only conjectured. This perfect completeness enables us to show the FPC undefinability of other problems whose NP-hardness is conjectured. In particular, we are able to show that no FPC formula can separate the 3-colourable graphs from those that are not t-colourable, for any constant t.
Cite as

Anuj Dawar and Bálint Molnár. Undefinability of Approximation of 2-To-2 Games. In 33rd EACSL Annual Conference on Computer Science Logic (CSL 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 326, pp. 16:1-16:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{dawar_et_al:LIPIcs.CSL.2025.16,
  author =	{Dawar, Anuj and Moln\'{a}r, B\'{a}lint},
  title =	{{Undefinability of Approximation of 2-To-2 Games}},
  booktitle =	{33rd EACSL Annual Conference on Computer Science Logic (CSL 2025)},
  pages =	{16:1--16:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-362-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{326},
  editor =	{Endrullis, J\"{o}rg and Schmitz, Sylvain},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2025.16},
  URN =		{urn:nbn:de:0030-drops-227735},
  doi =		{10.4230/LIPIcs.CSL.2025.16},
  annote =	{Keywords: Hardness of Approximation, Unique Games, Descriptive Complexity, Fixed-Point Logic with Counting}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2023.58
Topological Universality of the Art Gallery Problem

Authors: Jack Stade and Jamie Tucker-Foltz

Published in: LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023)

Abstract
We prove that any compact semi-algebraic set is homeomorphic to the solution space of some art gallery problem. Previous works have established similar universality theorems, but holding only up to homotopy equivalence, rather than homeomorphism, and prior to this work, the existence of art galleries even for simple spaces such as the Möbius strip or the three-holed torus were unknown. Our construction relies on an elegant and versatile gadget to copy guard positions with minimal overhead. It is simpler than previous constructions, consisting of a single rectangular room with convex slits cut out from the edges. We show that both the orientable and non-orientable surfaces of genus n admit galleries with only O(n) vertices.
Cite as

Jack Stade and Jamie Tucker-Foltz. Topological Universality of the Art Gallery Problem. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 58:1-58:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{stade_et_al:LIPIcs.SoCG.2023.58,
  author =	{Stade, Jack and Tucker-Foltz, Jamie},
  title =	{{Topological Universality of the Art Gallery Problem}},
  booktitle =	{39th International Symposium on Computational Geometry (SoCG 2023)},
  pages =	{58:1--58:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-273-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{258},
  editor =	{Chambers, Erin W. and Gudmundsson, Joachim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.58},
  URN =		{urn:nbn:de:0030-drops-179082},
  doi =		{10.4230/LIPIcs.SoCG.2023.58},
  annote =	{Keywords: Art gallery, Homeomorphism, Exists-R, ETR, Semi-algebraic sets, Universality}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2018.43
Computational Topology and the Unique Games Conjecture

Authors: Joshua A. Grochow and Jamie Tucker-Foltz

Published in: LIPIcs, Volume 99, 34th International Symposium on Computational Geometry (SoCG 2018)

Abstract
Covering spaces of graphs have long been useful for studying expanders (as "graph lifts") and unique games (as the "label-extended graph"). In this paper we advocate for the thesis that there is a much deeper relationship between computational topology and the Unique Games Conjecture. Our starting point is Linial's 2005 observation that the only known problems whose inapproximability is equivalent to the Unique Games Conjecture - Unique Games and Max-2Lin - are instances of Maximum Section of a Covering Space on graphs. We then observe that the reduction between these two problems (Khot-Kindler-Mossel-O'Donnell, FOCS '04; SICOMP '07) gives a well-defined map of covering spaces. We further prove that inapproximability for Maximum Section of a Covering Space on (cell decompositions of) closed 2-manifolds is also equivalent to the Unique Games Conjecture. This gives the first new "Unique Games-complete" problem in over a decade. Our results partially settle an open question of Chen and Freedman (SODA, 2010; Disc. Comput. Geom., 2011) from computational topology, by showing that their question is almost equivalent to the Unique Games Conjecture. (The main difference is that they ask for inapproximability over Z_2, and we show Unique Games-completeness over Z_k for large k.) This equivalence comes from the fact that when the structure group G of the covering space is Abelian - or more generally for principal G-bundles - Maximum Section of a G-Covering Space is the same as the well-studied problem of 1-Homology Localization. Although our most technically demanding result is an application of Unique Games to computational topology, we hope that our observations on the topological nature of the Unique Games Conjecture will lead to applications of algebraic topology to the Unique Games Conjecture in the future.
Cite as

Joshua A. Grochow and Jamie Tucker-Foltz. Computational Topology and the Unique Games Conjecture. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 43:1-43:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{grochow_et_al:LIPIcs.SoCG.2018.43,
  author =	{Grochow, Joshua A. and Tucker-Foltz, Jamie},
  title =	{{Computational Topology and the Unique Games Conjecture}},
  booktitle =	{34th International Symposium on Computational Geometry (SoCG 2018)},
  pages =	{43:1--43:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-066-8},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{99},
  editor =	{Speckmann, Bettina and T\'{o}th, Csaba D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.43},
  URN =		{urn:nbn:de:0030-drops-87566},
  doi =		{10.4230/LIPIcs.SoCG.2018.43},
  annote =	{Keywords: Unique Games Conjecture, homology localization, inapproximability, computational topology, graph lift, covering graph, permutation voltage graph, cell}
}
  • Refine by Type
  • 7 Document/PDF
  • 5 Document/HTML

  • Refine by Publication Year
  • 5 2025
  • 1 2023
  • 1 2018

  • Refine by Author
  • 2 Stade, Jack
  • 2 Tucker-Foltz, Jamie
  • 1 Dawar, Anuj
  • 1 Grochow, Joshua A.
  • 1 Hou, Tao
  • Show More...

  • Refine by Series/Journal
  • 7 LIPIcs

  • Refine by Classification
  • 2 Theory of computation → Complexity theory and logic
  • 2 Theory of computation → Design and analysis of algorithms
  • 2 Theory of computation → Finite Model Theory
  • 2 Theory of computation → Problems, reductions and completeness
  • 1 Mathematics of computing → Topology
  • Show More...

  • Refine by Keyword
  • 2 ETR
  • 1 Approximation Algorithms
  • 1 Art Gallery Problem
  • 1 Art gallery
  • 1 Complexity
  • 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