AF: Small: Collaborative Research: Boolean function analysis meets stochastic design

  • De, Anindya (PD/PI)

Project: Research project

Project Details


This proposal aims to study two different types of algorithmic problems through the lens of Boolean function analysis. The first is chance-constrained optimization problems, in which the constraints are stochastic (defined in terms of random variables) and the aim is to find an assignment which satisfies the constraints with at least some minimum threshold probability. The second is inverse power index prob-lems, which arise from social choice theory; the canonical problem of this sort is to design a voting game achieving some given specification of the “power” that each voter should have over the outcome (known as a power index). As popular power indices such as Shapley-Shubik and Banzhaf power indices admit simple probabilistic definitions, such power index problems also fit the motif of ‘stochastic design problems’ (i.e. problems where the constraints are defined in terms of random variables).
Effective start/end date6/1/1812/31/18


  • National Science Foundation (CCF-1814706)


Explore the research topics touched on by this project. These labels are generated based on the underlying awards/grants. Together they form a unique fingerprint.