# Papers' abstracts for Robert Krauthgamer

## Stochastic Selection Problems with Testing

Chen Attias, Robert Krauthgamer, Retsef Levi and Yaron Shaposhnik.

We study the problem of a decision-maker having to select one of many competing alternatives (e.g., choosing between projects, designs, or suppliers) whose future revenues are a priori unknown and modeled as random variables of known probability distributions. The decision-maker can pay to test each alternative to reveal its specific revenue realization (e.g., by conducting market research), and her goal is to maximize the expected revenue of the selected alternative minus the testing costs. This model captures an interesting trade-off between gaining revenue of a high-yield alternative and spending resources to reduce the uncertainty in selecting it. The combinatorial nature of the problem leads to a dynamic programming (DP) formulation with high-dimensional state space that is computationally intractable. By characterizing the structure of the optimal policy, we derive efficient optimal and near-optimal policies that are simple and easy-to-compute. In fact, these policies are also myopic -- they only consider a limited horizon of one test. Moreover, our policies can be described using intuitive testing intervals' around the expected revenue of each alternative, and in many cases, the dynamics of an optimal policy can be explained by the interaction between the testing intervals of various alternatives.

## Revisiting the Set Cover Conjecture

In the Set Cover problem, the input is a ground set of n elements and a collection of m sets, and the goal is to find the smallest sub-collection of sets whose union is the entire ground set. In spite of extensive effort, the fastest algorithm known for the general case runs in time $O(mn 2^n)$ [Fomin et al., WG 2004]. In 2012, as progress seemed to halt, Cygan et al. [TALG 2016] have put forth the Set Cover Conjecture (SeCoCo), which asserts that for every fixed \epsilon>0, no algorithm with runtime $2^{(1-\epsilon)n} poly(m)$ can solve Set Cover, even if the input sets are of arbitrary large constant size. We propose a weaker conjecture, which we call Log-SeCoCo, that is similar to SeCoCo but allows input sets of size O(log n).

To support Log-SeCoCo, we show that its failure implies an algorithm that is faster than currently known for the famous Directed Hamiltonicity problem. Even though Directed Hamiltonicity has been studied extensively for over half a century, no algorithm significantly faster than $2^n poly(n)$ is known for it. In fact, we show a fine-grained reduction to Log-SeCoCo from a generalization of Directed Hamiltonicity, known as the nTree problem, which too can be solved in time $2^n poly(n)$ [Koutis and Williams, TALG 2016]. We further show an equivalence between solving the parameterized versions of Set Cover and of nTree significantly faster than their current known runtime. Finally, we show that even moderate runtime improvements for Set Cover with bounded-size sets would imply new algorithms for nTree and for Directed Hamiltonicity.

Our technical contribution is to reinforce Log-SeCoCo (and arguably SeCoCo) by reductions from other famous problems with known algorithmic barriers, and hope it will lead to more results in this vein, particularly reinforcing the Strong Exponential-Time Hypothesis (SETH) by reductions from other well-known problems.