DIMACS | Center for Discrete Mathematics and Theoretical Computer Science
We study the furthest pair with outliers problem, where the goal is to identify a given number of outlier points such that the diameter of the remaining pointset is minimized. This is closely related to various clustering problems such as the Max-k-diameter with outliers. We show that the furthest pair with outliers is NP-complete by a reduction from the independent set. Further, we share found limits of (in)approximability for the furthest pair with outliers for the usual ell-p metrics. We report that 4 + ε approximation is efficiently computable and that no PTAS exists for the problem.
A hypergraph ℋ on {1 ... n} is just a collection of subsets of {1 ... n}. We say that there is a "k-Venn diagram" in ℋ if there are k sets ( A1, ... , Ak ) in ℋ such that all 2k intersections ( B1 ∩ ... ∩ Bk ) are non-empty where each Bi can either be Ai or the complement of Ai (equivalently, if we draw the Venn diagram associated with (A1, ... , Ak), all the regions of this picture are nonempty). Our goal is to try to understand the following question: how many sets can our hypergraph ℋ have if it fails to contain a k-Venn diagram?
For each positive integer n, let Sn be the symmetric group on { 1,2, ..., n }. Then a group G is said to be locally embeddable into finite groups if for every finite subset F ⊂ G, there exists an injection φ : F → Sn for some n ≥ 1 such that whenever g, h, gh ∈ F, then φ(gh) = φ(g)φ(h). In this case, we say that G is an LEF group.
In the group theoretic literature, LEF groups are usually characterized in terms of embeddings into ultraproducts of finite symmetric groups. It is natural to ask whether there is a characterization in terms of the more concrete notion of a reduced product of finite symmetric groups. In more detail, let P = ∏n ≥ 1 Sn be the full direct product and let N be the normal subgroup of elements (πn) ∈ P such that πn = 1 for all but finitely many positive integers n. Then the reduced product is the quotient P0 = P/N.
We have shown that it is neither provable nor disprovable using the classical ZFC axioms of set theory that if G is a group such that |G| ≤ 2ℵ0, then G is an LEF group if and only if G embeds into P0. We have obtained results concerning characterizations in terms of nonprincipal ultrafilters. Certain subtle questions about the nature of the independence remain. We have obtained analogous results for sofic groups.
We examined a combinatorial game called Division game. There are 2n coins and two players, Alice and Bob, who want to split the coins so that each player has exactly n coins. In the first turn, Alice picks a coin and Bob decides who gets it. Then, the roles swap and the game continues until one of the players gets n coins. The other player then obtains the remaining coins and the player with the larger sum of coins wins the game. We conjecture that Bob always has a non-losing strategy which we proved for a small number of coins and for special classes of games.
We consider the problem of approximate clustering with the diameter objective function. When the number of clusters is allowed to be unbounded, the inapproximability ratio is fairly well understood. However, this problem has not been well-studied when the number of clusters is constant. In this work, we show improved hardness bounds when there are a fixed number of clusters. Specifically, we show that the problem is hard to approximate within a factor of 1.5 in Hamming space, and within 1.304 in Euclidean space. Additionally, we prove several barrier results to known methods of proving hardness, and we provide a polynomial time algorithm for the problem when the number of dimensions is constant.
In this article, we study the problem of classifying graphs that admit `KT orientations'. A~directed graph $G$ is said to have a KT orientation if there is at most one directed path between any pair of vertices of $G$. We extend the known examples of classes of graphs that admit a KT orientation and those graph families which do not. We show that the problem of determining whether a given graph admits a KT orientation is NP-complete, in particular this also applies if we restrict ourselves to planar graphs. Moreover we provide an algorithm to decide if a digraph with max-degree at most 3 has a KT orientation, while for graphs with max-degree $4$, this remains NP-complete. Finally we construct a graph family with small independence number (sub-linear in the number of vertices), and thus has unbounded fractional chromatic number, that admits a KT orientation.
In this project, we studied Steiner minimal trees for the points given by the corners of the regular simplex. We provide an explicit formula for the coordinates of the Steiner points of a conjectured Steiner minimal tree for simplexes of dimension 2k-1. Also, we explore the function APTC(T), a notion used to characterize trees with respect to the sum of all distances between the terminals, and proved that the conjectured topology for Steiner minimal trees for the regular simplex minimizes this function over all tree with n terminals and n-2 interior points.
This project primarily focused on the class NISZK_L, introduced in a paper from 2020 done with REU students and Eric Allender. Little was known about this class beyond the results in that paper and results from REU students the following summer, mainly comprising of two complete problems, hardness results relating to MKTP, and equivalence to a weaker subclass of NISZK, NISKZ_AC^0. This summer, we expanded these results to primarily show equivalences between NISZK_AC^0, NISZK_L, and NISZK_PM, among an array of other related results.
