Reference number : GC-2017-Q1-03337, amendment number : , agreement type : G, recipient legal name : Borodin, Allan (University of Toronto), recipient country : CA, recipient province : nan, recipient city : Ontario, recipient postal code : nan, program name english : Discovery Grants Program - Individual, program name french : Programme de subventions à la découverte - individuelles, program purpose english : This proposal concerns a number of different research areas. However, my recent research interests are often motivated by the question as to what can and cannot be computed by ``conceptually simple algorithms''. In this regard, my primary interest concerns conceptually simple approximation algorithms for combinatorial optimization problems. More specifically, I am studying various forms and extensions of online and greedy algorithms, primal dual algorithms, dynamic programming algorithms, local algorithms, and local search. And most recently, I have been concerned with domains where rather naive randomization can often outperform more ``principled'' and sophisticated deterministic algorithms. As examples, we can ask, what is the simplest deterministic one pass algorithm that can match or surpass the 3/4 approximation ratio achieved by various algorithms for the Max-Sat problem and the same question as to exceeding the 1-1/e approximation for online bipartite matching. In particular, I am studying parallel and multi-pass online and greedy algorithms. It has recently been shown that such algorithms can be sometimes be derived from randomized algorithms. However, so far there are only a couple of 
examples where randomized algorithms have been successfully de-randomized to become parallel algorithms. Furthermore, when such a de-randomization is possible, we do not know how much parallelism is required. 
 
My interest in conceptually simple algorithms has led me to various problems in the field of algorithmic game theory/mechanism design (AGT). One fundamental problem is when can good approximations be turned into good mechanisms given that self-interested agents are providing the inputs. 
For example, in auctions the underlying allocation algorithms needs to be conceptually simple for the auction mechanism to be adopted in practice. Perhaps the simplest type of auction mechanism is a posted price mechanism where agents (in some order) are offered prices for various bundles of goods and then must make a ``take it or leave it'' choice as to what to purchase. How such a mechanism price items or when there is no mechanism what are the eqquilibrium prices and what are the dynamics that can lead to equilibria. In the related field of social choice theory, I am also considering algorithmic questions concerning the use of various voting rules. And in other somewhat related fields, I am also interested in how influence spreads in a social network and how one achieves stable matchings given only partial (e.g. probabilistic) information as to preferences., program purpose french : This proposal concerns a number of different research areas. However, my recent research interests are often motivated by the question as to what can and cannot be computed by ``conceptually simple algorithms''. In this regard, my primary interest concerns conceptually simple approximation algorithms for combinatorial optimization problems. More specifically, I am studying various forms and extensions of online and greedy algorithms, primal dual algorithms, dynamic programming algorithms, local algorithms, and local search. And most recently, I have been concerned with domains where rather naive randomization can often outperform more ``principled'' and sophisticated deterministic algorithms. As examples, we can ask, what is the simplest deterministic one pass algorithm that can match or surpass the 3/4 approximation ratio achieved by various algorithms for the Max-Sat problem and the same question as to exceeding the 1-1/e approximation for online bipartite matching. In particular, I am studying parallel and multi-pass online and greedy algorithms. It has recently been shown that such algorithms can be sometimes be derived from randomized algorithms. However, so far there are only a couple of 
examples where randomized algorithms have been successfully de-randomized to become parallel algorithms. Furthermore, when such a de-randomization is possible, we do not know how much parallelism is required. 
 
My interest in conceptually simple algorithms has led me to various problems in the field of algorithmic game theory/mechanism design (AGT). One fundamental problem is when can good approximations be turned into good mechanisms given that self-interested agents are providing the inputs. 
For example, in auctions the underlying allocation algorithms needs to be conceptually simple for the auction mechanism to be adopted in practice. Perhaps the simplest type of auction mechanism is a posted price mechanism where agents (in some order) are offered prices for various bundles of goods and then must make a ``take it or leave it'' choice as to what to purchase. How such a mechanism price items or when there is no mechanism what are the eqquilibrium prices and what are the dynamics that can lead to equilibria. In the related field of social choice theory, I am also considering algorithmic questions concerning the use of various voting rules. And in other somewhat related fields, I am also interested in how influence spreads in a social network and how one achieves stable matchings given only partial (e.g. probabilistic) information as to preferences., agreement title english : Design, analysis and Theory of Algorithms, agreement title french : Design, analysis and Theory of Algorithms, agreement number : RGPIN, agreement value : 250000.0, agreement start date : 2017-05-10, agreement end date : nan, description english : nan, description french : nan, expected results english : nan, expected results french : nan, additional information english : Grant or Award spanning more than one fiscal year. (2017-2018 to 2022-2023), additional information french : Subvention ou bourse octroyée s'appliquant à plus d'un exercice financier. (2017-2018 à 2022-2023), owner organization : nserc-crsng, owner organization title : Natural Sciences and Engineering Research Council of Canada | Conseil de recherches en sciences naturelles et en génie du Canada