CoSP supported the last Research Experiences for Undergraduates (REU 2024) co-organized by Charles University, Faculty of Mathematics and Physics and Rutgers University, DIMACS. The first stage of the summer activity for talented young students took place at DIMACS from May 28 until July 19 2024. Students from Charles University worked on the following research projects:
Guillermo Gamboa, Todor Antić, Jelena Glišić, Patrik Zavoral: Approximability of Euclidean k-center and k-diameter
Abstract: 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 furhest pair with outliers for the usual $\ell_p$ metrics. We report that $4+\varepsilon$ approximation is efficiently computable and that no PTAS exists for the problem. Finally, we demonstrate our proof for $\sqrt{\frac{3}{2}}$-inapproximability of the problem under the $\ell_2$ metric.
The final group presentation is here.
Benjamín Benčík: Memory-query tradeoffs for property testing
Abstract: This project explores the trade-off between memory usage and query efficiency in graph property testing. Since this is a relatively new area of research, we establish a methodology for proving lower bounds on the product of memory and query complexities. Our analysis includes different graph models, and we provide specific algorithmic strategies for testing properties like the existence of k-star. Additionally, we consider randomized models with semi-random queries, aiming to detect k-cliques efficiently. Proving the lower bound on property testing k-cliques in the semi-random model is our current goal.
The final group presentation is here.
Adam Džavoronok, Jakub Šošovička, Tymofii Reizin: k-Venn Diagram
Abstract: We study extremal hypergraph problems dealing with a structure known as a Venn diagram. We apply the result of Keevash, Leader, Wagner, and Long for higher order Venn diagrams to obtain upper bound $O(n^{2^k-2k+1})$. Furthermore, we deal with the fixed uniformity case, where we obtained conjectured lower bound constructions of $\Omega(n^{2^{k-1}-1})$ for $k$-Venn diagram. Lastly, we present the best-known lower and upper bounds for the extremal problem of the 4-uniform 3-Venn Diagram.
The final group presentation is here.
Robert Jaworski: Understanding a platform's strategic entry into the marketplace
Abstract: Recent years have witnessed the rise of online marketplaces (e.g., Amazon, App Store) that create great convenience to facilitate matchings and improve economic efficiency. While these platforms use third-party sellers' data to facilitate better matchings, they have also leveraged those sales data to inform the decisions of entering the marketplace with their own products. We analyze historical data of Amazon products provided by Keepa.com in order to understand Amazon's entry strategy and analyze the impact on third party sellers.
The final group presentation is here.
Tymur Kotkov: Evaluating the Cooperative Potential of LLMs in Competitive Environment
Abstract: will be added
The final group presentation is here.
Volodymyr Kuznietsov, Sofiia Kotsiubynska: k-Stanley inequality
Abstract: will be added
Júlia Križanová, Filip Úradník, Rhett Olson (University of Minnesota-Twin Cities MN), Amanda Wang (Princeton University): Truth Learning in a Social and Adversarial Setting
Abstract: Sequential learning models situations where agents predict a ground truth in sequence, having access to their private, noisy measurements, and the predictions of agents who came earlier in the sequence. We study a generalization of this model to networks, where agents only see a subset of the previous agents' actions—those in their own neighborhood. We consider settings where agents are fully rational, as well as those where agents' rationality is bounded, only basing their decisions on a simple majority rule. The fraction of agents who predict the ground truth correctly depends heavily on the ordering in which the predictions are made. An important question in this area is whether there exists an ordering, under which the agents predict the ground truth correctly with high probability. We show that it is in fact NP-hard to answer this question for a general network for both full and bounded rationality of agents. Another natural question in this field is that of the resilience of a network to adversarial agents. We show the robustness of the widely-studied Celebrity graph.
The final group presentation is here.
Posted on 2024-07-21