教授简介 研究领域 学术成果
Nick Gravin is a full professor of computer science at Shanghai University of Finance and Economics. He completed his bachelor degree in mathematics at Saint-Pe-tersburg State University and two PhDs: first in mathematics from St. Petersburg Steklov institute of mathematics in Russia, and second in computer science from Nanyang Technological University. Dr. Gravin worked a postdoctoral researcher at Microsoft research New England and MIT. His research interests are in theoretical computer science and discrete mathematics and its intersections with economics, combinatorial optimisation, convex and discrete geometry, and probability theory. Dr. Gravin has WINE best paper award in 2018; Microsoft Asia fellowship in 2011.
theoretical computer science and discrete mathematics and its intersections with economics, combinatorial optimisation, convex and discrete geometry, and probability theory.
Works under submission/preparation
1. C. Daskalakis, N. Dikkala, N. Gravin. Testing from One Sample: Is the casino really using a riffle shuffle?(arxiv)
2.Y. Azar, M. Feldman, N. Gravin, A. Roytman. Liquid Price of Anarchy (arxiv)
3.N. Gravin, D. Pasechnik, B. Shapiro, M. Shapiro On moments of a polytope.(arxiv)
Publications
1. N. Gravin, Y. Peres, B. Sivan. (arxiv) Tight Lower Bounds for Multiplicative Weights Algorithmic Families. Forthcoming, ICALP 2017.
2. N. Gravin, N. Immorlica, B. Lucier, E. Pountourakis. (arxiv). Procrastination with Variable Present Bias. p.361, ACM EC 2016.
3. N. Gravin, Y. Peres, B. Sivan. (arxiv). Towards Optimal Algorithms for Prediction with Expert Advice. p. 528-547, SODA 2016.
4. N. Chen, N. Gravin, P. Lu. (arxiv) Competitive analysis via benchmark decomposition.p. 363-376, EC 2015.
5. M. Feldman, N Gravin, B. Lucier. (arxiv) Combinatorial Auctions via Posted Prices. p. 123--135, SODA 2015.
6. I. Caragiannis, A. Fanelli, N. Gravin. (arxiv) Short Sequences of Improvement Moves Lead toApproximate Equilibria in Constraint Satisfaction Games p. 49--60, SAGT 2014. 
7. N. Chen, N. Gravin, P. Lu (arxiv) Optimal Competitive Auctions. p. 253--262, STOC 2014.
8. N. Chen, N. Gravin, P. Lu. (arxiv) Truthful Generalized Assignments via Stable Matching. Mathematics of Operations Research p. 722-736, v. 39, n. 3, 2014
9. N. Gravin, P. Lu. (arxiv) Competitive Auctions for Markets with Positive Externalities. p. 569-580, ICALP 2013.
10. M. Feldman, N Gravin, B. Lucier. (arxiv) Combinatorial Walrasian Equilibrium p. 61-70, STOC 2013. 
11. M. Feldman, Hu Fu, N Gravin, B. Lucier. (arxiv) Simultaneous Auctions are (almost) Efficient p. 201-210, STOC 2013.
12.  Caragiannis, A. Fanelli, N. Gravin, A. Skopalik. Computing approximate pure Nash equilibria in congestion games. p. 26-29, SIGecom Exchanges 2012.
13.  Caragiannis, A. Fanelli, N. Gravin, A. Skopalik. (arxiv) Approximate Pure Nash Equilibria in Weighted Congestion Games: Existence, Efficient Computation, and Structure. p.284-301, EC 2012.
14. X. Bei, N. Chen, N. Gravin, P. Lu (arxiv) Budget Feasible Mechanism Design: From Prior-Free to Bayesian p. 449-458, STOC 2012.
15. Caragiannis, A. Fanelli, N. Gravin, A. Skopalik. (arxiv) Efficient computation of approximate pure Nash equilibria in congestion games. p. 532-541, FOCS 2011.
16. J. Augustine, N. Chen, E. Elkind, A. Fanelli, N. Gravin, D. Shiryaev. (arxiv) Dynamics of Profit-Sharing Games. p. 37-42, IJCAI 2011.
17. N. Chen, N. Gravin, P. Lu. (arxiv) On the Approximability of Budget Feasible Mechanisms. p. 685-699, SODA 2011.
18. J. Augustine, N. Gravin. (arxiv) On the Continuous CNN Problem. p. 254-265, ISAAC 2010.
19. N. Gravin. (pdf) Time optimal d-list colouring of a graph. p. 156-168, CSR 2010.
20. N. Chen, E. Elkind, N. Gravin, F. Petrov. (arxiv) Frugal Mechanism Design via Spectral Techniques. p. 755-764, FOCS 2010.
21. N. Chen, E. Elkind and N. Gravin. (pdf) Refining the Cost of Cheap Labor in Set System Auctions. p. 447-454, WINE 2009.
22. N. Gravin, F. Petrov, D. Shiryaev, S. Robins (arxiv) Poisson imitation of lattices and convex curves Mathematika, v. 60, i. 01, pp. 139- 152, 2014.
23. N. Gravin, M. Kolountzakis, S. Robins, D. Shiryaev. (arxiv) Structure results for multiple tilings in 3D Discrete and Computational Geometry. v. 50, i. 4, p. 1033-1050, 2013
24. N. Gravin, S. Robins, D. Shiryaev. (arxiv) Translational tilings by a polytope, with multiplicity. Combinatorica, v. 32, i. 6 , p. 629-649, 2012.
25. N. Gravin, J. Lasserre, D. Pasechnik, S. Robins (arxiv) The inverse moment problem for convex polytopes. Discrete and Computational Geometry, v. 48(3), p. 596-621, 2012.
26. N. Gravin, D. Karpov. (arxiv) On proper colorings of hypergraphs. (Russian)Zapiski Nauchnykh Seminarov POMI, v. 391, p. 79–89, 2011. English translation in Journal of Mathematical Sciences v. 184, i. 5, p. 595-600.
27. N. Chen, N. Gravin. (pdf) Note on Shortest k-Paths Problem. Journal of Graph Theory. v. 67(1), p. 34-37, 2011.
28. N. Gravin. (arxiv.org,PDMI preprints) Non-degenerate colorings in the Brook's theorem.
(in Russian)Diskretnay Matematika, v. 21-4, p. 106-128, 2009. Discrete Mathematics and Applications.
29. N. Gravin, D. Y. Shiryaev. (.pdfin Russian,translationin English) Abnormal subgroups of classical groups corresponding to closed sets of roots (Russian)Zap. Nauchn. Sem. POMI, v. 365, p. 151-171, 2009. Journal of Mathematical Sciences, v. 161:4, p. 542-552, 2009.
30. N. Gravin. (pdfin Russian) Construction of a spanning tree with many leaves. (in Russian)Zap. Nauchn. Sem. POMI p. 31-46, 2010. (translated into English by Springer in ``Journal of Mathematical Sciences'').
31. N. Gravin, D. Nguyen, D. Pasechnik, S. Robins. (arxiv) The Inverse Moment problem for convex polytopes: implementation aspects.
