DIMACS | Center for Discrete Mathematics and Theoretical Computer Science
We studied how to estimate out-of-sample and generalization error for Least Absolute Shrinkage and Selection Operator (LASSO) at each iteration of the Iterative Shrinkage-Thresholding Algorithm (ISTA). Our goal was to derive novel estimators for the aforementioned quantities as well as study their derivative structures. Due to the iterative nature of the problem, there was a natural connection to multitask learning. Thus the approach developed is analogous to an approach used to estimate these quantities in multitask learning. The results were confirmed with initial simulations.
The complexity of the minimum circuit size problem (MCSP) - and its many variants, including the minimum Kolgomorov time-complexity problem (MKTP) - is linked intricately to countless other questions in theoretical computer science. For instance, NP-hardness of MCSP or MKTP is known to imply ZPP ≠ EXP, and even if such reductions exist, they cannot be nearly as simple as the standard NP-completeness reductions for other problems. In this project, we study whether various variants of circuit minimization can be complete for NP, or smaller classes, under simple types of reductions. Specifically, we investigate the following questions. Can recent hardness results for MKTP be extended to MCSP? How important is adaptivity in NP-hardness reductions for circuit minimization? How robust is the recent definition of non-interactive statistical zero-knowledge with logspace-bounded verifiers and simulators?
A tournament on n agents is a binary relation that describes the outcomes of the $\binom{n}{2}$ matches played between two distinct agents. Tournaments play an important role not only in sporting events but in any setting where any two agents are comparable and some "most qualified" agent should be selected, such as elections. The winner of a tournament is determined by a tournament rule that maps tournaments to probability distributions over the agents. We want these rules to be fair (i.e., choose a high quality agent) and robust to strategic manipulation. Prior work has shown that under minimally fair rules, manipulations between two agents can be prevented when utility is nontransferable but not when utility is completely transferable. Motivated by the fact that neither utility model reflects reality, we consider pairwise manipulations under partially transferable utility. These situations arise, for example, when agents care about winning themselves but are still willing to collude if joint gains offset perceived individual losses. We show that previously studied tournament rules require high levels of selfishness in order to prevent pairwise manipulations and that for fixed levels of selfishness, there are always two agents who stand to gain a constant positive amount of probability under these rules by manipulating in large enough tournaments. We also show that for stronger notions of fairness, non-manipulable tournament rules are closely related to tournament rules that witness decreasing gains from manipulation as the number of agents increases. A major open question that remains is whether there is a tournament rule that is fair and non-manipulable for a fixed level of selfishness that meets the lower bound we prove. We conjecture that indeed such a rule exists.
In the recent light of the SARS-CoV-2 pandemic, the United States' response has proven to be incredibly poor with respect to policy decisions made on the local and federal levels. With deaths totaling at 142,755, this is more than the number of battle deaths in the Vietnam War, Korean War, and World War I combined. One of the easiest ways to prevent such an outbreak from reoccurring has shown to be a stronger implementation of policies on all governmental levels. Three categories which require more heavy implementation include Test, Track, and Treat (TTT), Distance, Isolate, Mask (DIM), and Prepare & Organize, Lead & Inform, Coordinate & Yaager results (POLICY). The American response was not sufficient enough to prevent mass infections and fatalities, and analysis of state and federal policies with respect to COVID-19 containment outstandingly point to a need for more drastic policy decisions.
Feder and Subi conjectured that for any 2-coloring of edges of the hypercube Qn, there always exists a pair of antipodal vertices connected by a shortest path which changes color at most once. Leader and Long proved that there always exists a path between antipodal vertices with at most n/2 changes and Dvorak improved this bound to (3/8+o(1))n. We give some partial results which may lead to further improvements of Dvorak's upper bound.
