Picture of Nick Gravin Nick Gravin

I am a full Professor at
School of Information Management and Engineering
Shanghai University of Finance and Economics
EMAIL: nikolai (*) mail (dot) shufe (dot) edu (dot) cn

Link to my page at SHUFE.

This page is no longer maintained: My New Page



Live journal account
userinfo sin_nikolaus
(in Russian)


free counters

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

    Computer Science
  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 to
    Approximate Equilibria in Constraint Satisfaction Games
    p. 49--60, SAGT 2014.
    Journal version accepted to Algorithmica
  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.
    Journal version to appear in SIAM Journal of Computing
  11. M. Feldman, Hu Fu, N Gravin, B. Lucier. (arxiv)
    Simultaneous Auctions are (almost) Efficient
    p. 201-210, STOC 2013.
    (Invited to the special issue of Games and Economic Behavior)
  12. I. Caragiannis, A. Fanelli, N. Gravin, A. Skopalik.
    Computing approximate pure Nash equilibria in congestion games.
    p. 26-29, SIGecom Exchanges 2012.
  13. I. 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.
    (Invited to the special issue of ACM Transactions on Economics and Computation)
  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. I. 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.
Mathematics
  1. 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.
  2. 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
  3. N. Gravin, S. Robins, D. Shiryaev. (arxiv)
    Translational tilings by a polytope, with multiplicity.
    Combinatorica, v. 32, i. 6 , p. 629-649, 2012.
  4. 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.
  5. 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.
  6. N. Chen, N. Gravin. (pdf)
    Note on Shortest k-Paths Problem.
    Journal of Graph Theory. v. 67(1), p. 34-37, 2011.
  7. 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.
  8. N. Gravin, D. Y. Shiryaev. (.pdf in Russian, translation in 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.
  9. N. Gravin. (pdf in 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'').
Technical reports
  1. N. Gravin, D. Nguyen, D. Pasechnik, S. Robins. (arxiv)
    The Inverse Moment problem for convex polytopes: implementation aspects.
    2014.

PhD Theses

  1. Thesis at PDMI (in Russian). Some aspects of proper graph colouring.
  2. Thesis at NTU. Incentive Compatible Design of Reverse Auctions.