2 papers
cs.CC2016
Pseudodeterministic Constructions in Subexponential Time
Igor C. Oliveira, Rahul Santhanam
We study pseudodeterministic constructions, i.e., randomized algorithms which output the same solution on most computation paths. We establish unconditionally that there is an infi…
cs.SI2012
Macroscopes: models for collective decision making
Subramanian Ramamoorthy, András Z. Salamon, Rahul Santhanam
We introduce a new model of collective decision making, when a global decision needs to be made but the parties only possess partial information, and are unwilling (or unable) to f…