Nikolai Gravin

教授、博士生导师

研究方向：理论计算机科学和离散数学及其与经济学的交叉

教授简介研究领域学术成果

1.&nbsp;N. Gravin, Y. Peres, B. Sivan. (arxiv)&nbsp;Tight Lower Bounds for Multiplicative Weights Algorithmic Families. Forthcoming, ICALP 2017.

2.&nbsp;N. Gravin, N. Immorlica, B. Lucier, E. Pountourakis. (arxiv). Procrastination with Variable Present Bias. p.361, ACM EC 2016.

3.&nbsp;N. Gravin, Y. Peres, B. Sivan. (arxiv). Towards Optimal Algorithms for Prediction with Expert Advice.&nbsp;p. 528-547, SODA 2016.

4.&nbsp;N. Chen, N. Gravin, P. Lu.&nbsp;(arxiv)&nbsp;Competitive analysis via benchmark decomposition.p. 363-376, EC 2015.

5.&nbsp;M. Feldman, N Gravin, B. Lucier. (arxiv)&nbsp;Combinatorial Auctions via Posted Prices.&nbsp;p. 123--135, SODA 2015.

6.&nbsp;I. Caragiannis, A. Fanelli, N. Gravin. (arxiv)&nbsp;Short Sequences of Improvement Moves Lead toApproximate Equilibria in Constraint Satisfaction Games&nbsp;p. 49--60, SAGT 2014.&nbsp;

7.&nbsp;N. Chen, N. Gravin, P. Lu (arxiv)&nbsp;Optimal Competitive Auctions.&nbsp;p. 253--262, STOC 2014.

8.&nbsp;N. Chen, N. Gravin, P. Lu. (arxiv)&nbsp;Truthful Generalized Assignments via Stable Matching.&nbsp;Mathematics of Operations Research p. 722-736, v. 39, n. 3, 2014

9.&nbsp;N. Gravin, P. Lu. (arxiv)&nbsp;Competitive Auctions for Markets with Positive Externalities.&nbsp;p. 569-580, ICALP 2013.

10.&nbsp;M. Feldman, N Gravin, B. Lucier. (arxiv)&nbsp;Combinatorial Walrasian Equilibrium&nbsp;p. 61-70, STOC 2013.&nbsp;

11.&nbsp;M. Feldman, Hu Fu, N Gravin, B. Lucier. (arxiv)&nbsp;Simultaneous Auctions are (almost) Efficient&nbsp;p. 201-210, STOC 2013.

12.&nbsp;&nbsp;Caragiannis, A. Fanelli, N. Gravin, A. Skopalik.&nbsp;Computing approximate pure Nash equilibria in congestion games.&nbsp;p. 26-29, SIGecom Exchanges 2012.

13.&nbsp;&nbsp;Caragiannis, A. Fanelli, N. Gravin, A. Skopalik. (arxiv)&nbsp;Approximate Pure Nash Equilibria in Weighted Congestion Games:&nbsp;Existence, Efficient Computation, and Structure.&nbsp;p.284-301, EC 2012.

14.&nbsp;X. Bei, N. Chen, N. Gravin, P. Lu (arxiv)&nbsp;Budget Feasible Mechanism Design: From Prior-Free to Bayesian&nbsp;p. 449-458, STOC 2012.

15.&nbsp;Caragiannis, A. Fanelli, N. Gravin, A. Skopalik. (arxiv)&nbsp;Efficient computation of approximate pure Nash equilibria in congestion games.&nbsp;p. 532-541, FOCS 2011.

16.&nbsp;J. Augustine, N. Chen, E. Elkind, A. Fanelli, N. Gravin, D. Shiryaev. (arxiv)&nbsp;Dynamics of Profit-Sharing Games.&nbsp;p. 37-42, IJCAI 2011.

17.&nbsp;N. Chen, N. Gravin, P. Lu. (arxiv)&nbsp;On the Approximability of Budget Feasible Mechanisms.&nbsp;p. 685-699, SODA 2011.

18.&nbsp;J. Augustine, N. Gravin. (arxiv)&nbsp;On the Continuous CNN Problem.&nbsp;p. 254-265, ISAAC 2010.

19.&nbsp;N. Gravin. (pdf)&nbsp;Time optimal d-list colouring of a graph.&nbsp;p. 156-168, CSR 2010.

20.&nbsp;N. Chen, E. Elkind, N. Gravin, F. Petrov. (arxiv)&nbsp;Frugal Mechanism Design via Spectral Techniques.&nbsp;p. 755-764, FOCS 2010.

21.&nbsp;N. Chen, E. Elkind and N. Gravin. (pdf)&nbsp;Refining the Cost of Cheap Labor in Set System Auctions.&nbsp;p. 447-454, WINE 2009.

22.&nbsp;N. Gravin, F. Petrov, D. Shiryaev, S. Robins (arxiv)&nbsp;Poisson imitation of lattices and convex curves&nbsp;Mathematika, v. 60, i. 01, pp. 139- 152, 2014.

23.&nbsp;N. Gravin, M. Kolountzakis, S. Robins, D. Shiryaev. (arxiv)&nbsp;Structure results for multiple tilings in 3D&nbsp;Discrete and Computational Geometry. v. 50, i. 4, p. 1033-1050, 2013

24.&nbsp;N. Gravin, S. Robins, D. Shiryaev. (arxiv)&nbsp;Translational tilings by a polytope, with multiplicity.&nbsp;Combinatorica, v. 32, i. 6 , p. 629-649, 2012.

25.&nbsp;N. Gravin, J. Lasserre, D. Pasechnik, S. Robins (arxiv)&nbsp;The inverse moment problem for convex polytopes.&nbsp;Discrete and Computational Geometry, v. 48(3), p. 596-621, 2012.

26.&nbsp;N. Gravin, D. Karpov. (arxiv)&nbsp;On proper colorings of hypergraphs.&nbsp;(Russian)Zapiski Nauchnykh Seminarov POMI, v. 391, p. 79–89, 2011.&nbsp;English translation in Journal of Mathematical Sciences v. 184, i. 5, p. 595-600.

27.&nbsp;N. Chen, N. Gravin. (pdf)&nbsp;Note on Shortest k-Paths Problem.&nbsp;Journal of Graph Theory. v. 67(1), p. 34-37, 2011.

28.&nbsp;N. Gravin. (arxiv.org,PDMI preprints)&nbsp;Non-degenerate colorings in the Brook&#39;s theorem.
(in Russian)Diskretnay Matematika, v. 21-4, p. 106-128, 2009.&nbsp;Discrete Mathematics and Applications.

29.&nbsp;N. Gravin, D. Y. Shiryaev. (.pdfin Russian,translationin English)&nbsp;Abnormal subgroups of classical groups corresponding to closed sets of roots&nbsp;(Russian)Zap. Nauchn. Sem. POMI, v. 365, p. 151-171, 2009.&nbsp;Journal of Mathematical Sciences, v. 161:4, p. 542-552, 2009.

30.&nbsp;N. Gravin. (pdfin Russian)&nbsp;Construction of a spanning tree with many leaves.&nbsp;(in Russian)Zap. Nauchn. Sem. POMI p. 31-46, 2010.&nbsp;(translated into English by Springer in ``Journal of Mathematical Sciences&#39;&#39;).

31. N. Gravin, D. Nguyen, D. Pasechnik, S. Robins. (arxiv)&nbsp;The Inverse Moment problem for convex polytopes: implementation aspects.

-->

Research papers

Works under submission/preparation

1. C. Daskalakis, N. Dikkala, N. Gravin.&nbsp;Testing from One Sample: Is the casino really&nbsp;using a riffle shuffle?(arxiv)

2.Y. Azar, M. Feldman, N. Gravin, A. Roytman.&nbsp;Liquid Price of Anarchy&nbsp;(arxiv)

3.N. Gravin, D. Pasechnik, B. Shapiro, M. Shapiro&nbsp;On moments of a polytope.(arxiv)

Publications