Search
Now showing items 21-24 of 24
Improved Algorithms for Variants of Bin Packing and Knapsack
We study variants of two classical optimization problems: Bin Packing and Knapsack. Both bin packing and knapsack fall under the regime of "Packing and Covering Problems". In bin packing, we are given a set of input items, ...
Specification Synthesis with Constrained Horn Clauses
Many practical problems in software development, verification and testing rely on specifications. The problem of specification synthesis is to automatically find relational constraints for undefined functions, called ...
Rational Secure Computation: New Definitions and Constructions
Cryptography and Game Theory are two fascinating areas of modern computing, and there have been numerous works since the early 2000s to bridge these. While cryptography provides mechanisms to detect deviations, game theory ...
Bandit Algorithms: Fairness, Welfare, and Applications in Causal Inference
We study regret in online learning from a welfarist perspective and explore an application of
bandit algorithms in causal inference. We introduce Nash regret, which measures the difference
between the optimal action ...