 |
Topological Universality of the Art Gallery Problem.
Jack Stade and
Jamie Tucker-Foltz.
39th International Symposium on Computational Geometry,
June 2023.
►Abstract
[ PDF ]
[ arXiv ]
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 require galleries with only O(n) vertices.
|
SoCG 2023
|
|
|
 |
Representation with Incomplete Votes.
Daniel Halpern,
Gregory Kehne,
Ariel D. Procaccia,
Jamie Tucker-Foltz, and
Manuel Wüthrich.
37th AAAI Conference on Artificial Intelligence,
February 2023.
►Abstract
[ PDF ]
Platforms for online civic participation rely heavily on methods for condensing thousands of comments into a relevant handful based on whether participants agree or disagree with them. We argue that these methods should guarantee fair representation of the participants, as their outcomes may affect the health of the conversation and inform impactful downstream decisions. To that end, we draw on the literature on approval-based committee elections. Our setting is novel in that the approval votes are incomplete since participants will typically not vote on all comments. We prove that this complication renders non-adaptive algorithms impractical in terms of the amount of information they must gather. Therefore, we develop an adaptive algorithm that uses information more efficiently by presenting incoming participants with statements that appear promising based on votes by previous participants. We prove that this method satisfies commonly used notions of fair representation, even when participants only vote on a small fraction of comments. Finally, an empirical evaluation on real data shows that the proposed algorithm provides representative outcomes in practice.
|
AAAI 2023
|
|
|
 |
Thou Shalt Covet The Average Of Thy Neighbors' Cakes.
Jamie Tucker-Foltz.
Information Processing Letters,
November 2022.
►Abstract
[ PDF ]
[ arXiv ]
[ Official journal version ]
We prove an Ω(n^2) lower bound on the query complexity of local proportionality in the Robertson-Webb cake-cutting model. Local proportionality requires that each agent prefer their allocation to the average of their neighbors' allocations in some undirected social network. It is a weaker fairness notion than envy-freeness, which also has query complexity Ω(n^2), and generally incomparable to proportionality, which has query complexity Θ(n log n). This result separates the complexity of local proportionality from that of ordinary proportionality, confirming the intuition that finding a locally proportional allocation is a more difficult computational problem.
|
IPL 2022
|
|
|
 |
Can Buyers Reveal for a Better Deal?
Daniel Halpern,
Gregory Kehne, and
Jamie Tucker-Foltz.
31st International Joint Conference on Artificial Intelligence,
July 2022.
►Abstract
[ PDF ]
[ arXiv ]
We study market interactions in which buyers are allowed to credibly reveal partial information about their types to the seller. Previous recent work has studied the special case of one buyer and one good, showing that such communication can simultaneously improve social welfare and ex ante buyer utility. However, with multiple buyers, we find that the buyer-optimal signalling schemes from the one-buyer case are actually harmful to buyer welfare. Moreover, we prove several impossibility results showing that, with either multiple i.i.d. buyers or multiple i.i.d. goods, maximizing buyer utility can be at odds with social efficiency, which is surprising in contrast with the one-buyer, one-good case. Finally, we investigate the computational tractability of implementing desirable equilibrium outcomes. We find that, even with one buyer and one good, optimizing buyer utility is generally NP-hard but tractable in a practical restricted setting.
|
IJCAI 2022
|
|
|
 |
Compact Redistricting Plans Have Many Spanning Trees.
Ariel D. Procaccia and
Jamie Tucker-Foltz.
ACM-SIAM Symposium on Discrete Algorithms,
January 2022.
►Abstract
[ PDF ]
[ arXiv ]
[ 20 minute SODA talk ]
[ 60 minute talk at Copenhagen-Jerusalem Combinatorics Seminar ]
In the design and analysis of political redistricting maps, it is often useful to be able to sample from the space of all partitions of the graph of census blocks into connected subgraphs of equal population. There are influential Markov chain Monte Carlo methods for doing so that are based on sampling and splitting random spanning trees. Empirical evidence suggests that the distributions such algorithms sample from place higher weight on more "compact" redistricting plans, which is a practically useful and desirable property. In this paper, we confirm these observations analytically, establishing an inverse exponential relationship between the total length of the boundaries separating districts and the probability that such a map will be sampled. This result provides theoretical underpinnings for algorithms that are already making a significant real-world impact.
|
SODA 2022
|
|
|
 |
Inapproximability of Unique Games in Fixed-Point Logic with Counting.
Jamie Tucker-Foltz.
36th Annual Symposium on Logic in Computer Science,
July 2021.
★ Best student paper
►Abstract
[ PDF ]
[ arXiv ]
[ LICS paper ]
[ 15 minute LICS talk ]
[ 60 minute talk at UMass CS Theory Seminar ]
We study the extent to which it is possible to approximate the optimal value of a Unique Games instance in Fixed-Point Logic with Counting (FPC). We prove two new FPC-inexpressibility results for Unique Games: the existence of a (1/2, 1/3 + delta)-inapproximability gap, and inapproximability to within any constant factor. Previous recent work has established similar FPC-inapproximability results for a small handful of other problems. Our construction builds upon some of these ideas, but contains a novel technique. While most FPC-inexpressibility results are based on variants of the CFI-construction, ours is significantly different.
|
LICS 2021
|
|
|
 |
Multiagent Evaluation Mechanisms.
Tal Alon,
Magdalen Dobson,
Ariel D. Procaccia,
Inbal Talgam-Cohen, and
Jamie Tucker-Foltz.
6th World Congress of the Game Theory Society,
July 2021.
34th AAAI Conference on Artificial Intelligence,
February 2020.
►Abstract
[ PDF ]
[ Download AAAI paper ]
[ 20 minute GAMES talk ]
We consider settings where agents are evaluated based on observed features, and assume they seek to achieve feature values that bring about good evaluations. Our goal is to craft evaluation mechanisms that incentivize the agents to invest effort in desirable actions; a notable application is the design of course grading schemes. Previous work has studied this problem in the case of a single agent. By contrast, we investigate the general, multi-agent model, and provide a complete characterization of its computational complexity.
|
GAMES 2021
AAAI 2020
|
|
|
 |
A Cut And Choose Mechanism to Prevent Gerrymandering.
Jamie Tucker-Foltz.
29th International Conference on Game Theory,
July 2018.
►Abstract
[ PDF ]
[ arXiv ]
This paper presents a novel mechanism to endogenously determine the fair division of a state into electoral districts in a two-party setting. No geometric constraints are imposed on voter distributions or district shapes; instead, it is assumed that any partition of the population into districts of equal population is feasible. One party divides the map, then the other party chooses a minimum threshold level of support needed to win a district. Districts in which neither party meets this threshold are awarded randomly. Despite the inherent asymmetry, the equilibria of this mechanism always yield fair outcomes, up to integer rounding.
|
Stony Brook 2018
|
|
|
 |
Computational Topology and the Unique Games Conjecture.
Joshua A. Grochow and
Jamie Tucker-Foltz.
34th International Symposium on Computational Geometry,
June 2018.
►Abstract
[ PDF ]
[ Download SoCG paper ]
[ arXiv ]
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 2004 and SICOMP, 2007) 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 and 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/2Z, and we show Unique Games-completeness over Z/kZ 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.
|
SoCG 2018
|
|
|
 |
Witness Complexes for Time Series Analysis.
Nicole Sanderson,
Jamie Tucker-Foltz,
Elizabeth Bradley, and
James D. Meiss.
SIAM Conference on Applications of Dynamical Systems (workshop),
May 2017.
►Abstract
[ Download slides ]
[ 20 minute talk by Nicole Sanderson ]
A scalar time-series can be "unfolded" into R^d by delay coordinate reconstruction. In the best case, this gives an attractor that is topologically equivalent to that of the underlying dynamical system. We can then compute the persistent homology of the data using a variety of complexes, e.g., Cech, Vietoris-Rips, or alpha. To be more computationally efficient we use a witness complex: it can provide a sparser representation and yet be faithful to the homology. Topologically accurate delay reconstruction requires choice of appropriate values for a d and a time delay. In practice, these must be estimated from the data, and the estimation procedures are heuristic and often problematic. Recent work of Garland et al. demonstrates that accurate persistent homology computations are possible from witness complexes built from delay reconstructions with d below that demanded by the theory. Following this, we introduce novel witness relations that incorporate time and explore the robustness of the resulting homology with respect to choice of delay. We utilize the witness map, a multivalued map on the witness complex induced by the temporal ordering of the data and velocity estimates. The new relations seek to inhibit data points from witnessing landmarks traveling in disparate directions and that are on distinct branches of an attractor, as these can suggest a false connection, due to the particular reconstruction.
|
DS 2017
|
|
|
Harvard University