Joseph Fluegemann
Ph.D. Candidate
Education
- M.S. (2017) San Jose State University, mathematics
- B.A. (2013) University of California at Berkeley, cognitive science
Éva Tardos
Jacob Gould Schurman Professor
Publications
Network Games and extensions
- T. Roughgarden and E. Tardos: How Bad is Selfish Routing? Journal of the ACM, 2002, Volume 49 , Issue 2. Preliminary version has appeared in the Proceedings of the 41st Annual IEEE Symposium on the Foundations of Computer Science, 2000.
- T. Roughgarden and E. Tardos: Bounding the Inefficiency of Equilibria in Nonatomic Congestion Games. Games and Economic Behaviour, Volume 47, Issue 2, May 2004, Pages 389-403.
- H. Lin, T. Roughgarden, and E. Tardos, Bounding Braess's Paradox, Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms, 2004.
- H. Lin, T. Roughgarden, E. Tardos, and A. Walkover. Braess's Paradox, Fibonacci Numbers, and Exponential Inapproximability, in the 32nd International Colloquium on Automata, Languages and Programming (ICALP,05) July, 2005.
- E. Anshelevich, A. Dasgupta, É. Tardos, T. Wexler, Near-optimal network design with selfish agents, in the proceedings of the Annual ACM Symposium on the Theory of Computing, 2003.
- E. Anshelevich, A. Dasgupta, J. Kleinberg, E. Tardos, T. Wexler, and T. Roughgarden. The Price of Stability for Network Design with Fair Cost Allocation, Annual IEEE Symposium on Foundations of Computer Science, 2004.
- Eva Tardos. Network Games. Proceedings of the Annual ACM Symposium on Theory of Computing, 2004.
- Ara Hayrapetyan, Éva Tardos and Tom Wexler - A Network Pricing Game for Selfish Traffic Distributed Computing, (PODC'05 special issue).Preliminary version appeared in the Proceedings of
24th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC'05), July 2005. - Ara Hayrapetyan, Éva Tardos and Tom Wexler: Effect of Collusion in Congestion Games. Proceedings of the ACM Symposium on the Theory of Computing (STOC), 2006.
- L. Blume, D. Easley, J. Kleinberg and E. Tardos: Trading Networks with Price-Setting Agents to appear in EC'07.
Mechanism Design
- A. Archer and 'E. Tardos: Frugal Path mechanisms, to appear in Transaction on Algorithms. Preliminary version appeared in the Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, 2002, pp. 991-999.
- A. Archer and E. Tardos: Truthful mechanisms for one-parameter agents, Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science (2001) 482-491.
- A. Archer, Christos Papadimitriou, Kunal Talwar, Eva Tardos: An approximate truthful mechanism for combinatorial auctions with single parameter agents. Internet Mathematics, Volume 1 Issue 2, 2004. Prleiminary version appeared in the Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, 2003, pp. 205 - 214.
- M. Pal and E. Tardos: Group Strategyproof Mechanisms via Primal-Dual Algorithms, in the Proceedings of the Annual IEEE Symposium on Foundations of Computer Science, 2003.
- A. Gupta, A. Srinivasan, and E. Tardos. Cost-Sharing Mechanisms for Network Design. Proceedings of APPROX 2004.
Social Networks
- David Kempe, Jon Kleinberg, Éva Tardos: Maximizing the Spread of Influence in a Social Network.
Proceedings of KDD 2003, Washington DC. - David Kempe, Jon Kleinberg, Éva Tardos: Influential Nodes in a Diffusion Model for Social Networks. In Proceedings of ICALP 2005, Lisboa, Portugal.
Classification
- J. Kleinberg and E. Tardos. Approximation Algorithms for Classification Problems with Pairwise Relationships:
Metric Partitioning and Markov Random Fields, Journal of the ACM, 2002, Volume 49, Issue 5, pp, 616-639. Preliminary version has appeared in the Proceedings of the 40th Annual IEEE Symposium on the Foundations of Computer Science, 1999. - A. Gupta and E. Tardos: A Constant Factor Approximation Algorithm for a Class of Classification Problems, In the Proceedings of the ACM Symposium on the Theory of Computing, May 2000.
- A. Archer J. Fakcharoenphol, C. Harrelson, R. Krauthgamer, K. Talvar and E. Tardos: Approximate Classification via Earthmover Metrics, in the Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms, 2004.
Clustering and facility location
- Zoya Svitkina and Eva Tardos: Facility Location with Hierarchical Facility Costs. in the Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms, 2006.
- Martin Pál, Éva Tardos, Tom Wexler. Facility Location with Hard Capacities. In the Proceedings of the 42nd Annual IEEE Symposium on the Foundations of Computer Science, 2001.
- D. B. Shmoys, E. Tardos and K. Aardal. Approximation algorithms for the facility location problem.
In the Proc. of the 29th Annual ACM Symposium on the Theory of Computing, 1997, pp. 265-274. - M. Charikar, S. Guha, E. Tardos and D. Shmoys. A constant-factor approximation algorithm for the k-median problem. To appear in the JCSS, preliminary version has appeared in the Proc. of the 31st Annual ACM Symposium on the Theory of Computing, 1999, pp. 1-10.
- Ara Hayrapetyan, Chaitanya Swamy and Éva Tardos: Network Design for Information Networks, ACM-SIAM Symposium on Discrete Algorithms (SODA), 2005
Network Design
- M. Goemans, A. Goldberg, S. Plotkin, D. Shmoys, E. Tardos, and D. Williamson: Improved approximation algorithms for network design problems. In the proceeding of the 5th Annual ACM-SIAM Symposium on Discrete Algorithms, January 1994, pp. 223-232. ORIE TR-1116.
- V. Melkonian and E. Tardos. Approximation Algorithms for a Directed Network Design Problem.
In the Proceedings of the 7th International Integer Programming and Combinatorial Optimization Conference (IPCO'99), Graz, 1999. - Ara Hayrapetyan, Chaitanya Swamy and Éva Tardos - Network Design for Information Networks
- Zoya Svitkina and Éva Tardos: Facility Location with Hierarchical Facility Costs.
Routing Disjoint Paths and Packets in Networks
- J. Kleinberg, Y. Rabani, and E. Tardos. Fairness in Routing and Load Balancing, In the Proceedings of the 40th Annual IEEE Symposium on the Foundations of Computer Science, 1999.
- J. Kleinberg and E. Tardos: Approximations for the Disjoint Paths Problem in High-Diameter Planar Networks, Journal of Computer and System Sciences STOC'95 special issue, vol 57, pp 61-73, 1998. Preliminary version has appeared in the Proceedings of the 27th Annual ACM Symposium on the Theory of Computing, 1995, pp. 26-35. ORIE TR-1121.
- J. Kleinberg and E. Tardos: Disjoint Paths in Densely Embedded Graphs, In the Proceedings of the 34th Annual IEEE Symposium on the Foundations of Computer Science, 1995, pp. 52-61.
- Y. Rabani and E. Tardos: Distributed Packet Switching in Arbitrary Networks, in the 28th ACM Symposium on Theory of Computing, May, 1996, pp. 366-376.
Scheduling
- D. Shmoys and E. Tardos, An approximation algorithm for the generalized assignment problem. Mathematical Programming A 62, 1993, 461-474. Preliminary version has appeared in the proceeding of the 4th Annual ACM-SIAM Symposium on Discrete Algorithms, January 1993.
- A. Goel, M. Henzinger, S. Plotkin, and E. Tardos. Scheduling Data Transfers in a Network and the Set Scheduling Problem In the Proc. of the 31st Annual ACM Symposium on the Theory of Computing, 1999, pp. 189-199.
Generalized Flow
- A. Goldberg, S. Plotkin, E. Tardos: Combinatorial algorithms for the generalized circulation problem, Mathematics of Operations Research, 16/2, 1991, 351-381. Preliminary version has appeared in the Proceedings of the 29th Annual IEEE Symposium on the Foundations of Computer Science (1988), 432-443.
- E. Tardos and K. Wayne. Simple Generalized Maximum Flow Algorithms. Proceedings of the 6th International Integer Programming and Combinatorial Optimization Conference (IPCO'98), Houston, 1998, pp. 310-324.
Packing and Covering Algorithms
- P. Klein, S. Plotkin, C. Stein and E. Tardos, Faster approximation algorithms for the unit capacity concurrent flow problem with applications to routing and finding sparse cuts. SIAM Journal on Computing, 23/3, 1994,. 466-487. Preliminary version has appeared in the proceedings of the 22nd Annual ACM Symposium on the Theory of Computing (1990), 310-321.
- T. Leighton, F. Makedon, S. Plotkin, C. Stein, E. Tardos, S. Tragoudas: Fast Approximation Algorithms for Multicommodity Flow Problems, Journal of Computer and System Sciences, 50 (STOC'91 special issue), 1995, pp. 228--243. Preliminary version has appeared in the Proceedings of the 23rd Annual ACM Symposium on the Theory of Computing (1991), 101-110.
- S.A. Plotkin, D. Shmoys, and E. Tardos, Fast approximation algorithms for fractional packing and covering problems, to appear in Mathematics of Operations Research. ORIE TR-999. Preliminary version has appeared in the Proceedings of the 32nd Annual IEEE Symposium on the Foundations of Computer Science (1991), 495-505.
Networks with transit times
- B. Hoppe and E. Tardos: Polynomial Time Algorithms for Some Evacuation Problems. In the proceeding of the 5th Annual ACM-SIAM Symposium on Discrete Algorithms, January 1994, pp. 433-441. .
- B. Hoppe and E. Tardos: The Quickest Transshipment Problem, journal version of the paper in the proceeding of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms, 1995 pp. 512-521.
- L. Fleischer and E. Tardos. Efficient Continuous-Time Dynamic Network Flow Algorithms. Operations Research Letters 23 (1998) pp. 71-80.
Effective bandwidth
- J. Kleinberg, Y. Rabani and E. Tardos. Allocating Bandwidth for Bursty Connection. Journal version of the paper in the Proceedings of the 29th ACM Symposium on Theory of Computing, May, 1997, pp. 664-673.
Finding cuts in graphs
- S.A. Plotkin and E. Tardos, Improved Bounds on the Max-flow Min-cut Ratio for Multicommodity Flows. Combinatorica. Preliminary version has appeared in the Proceedings of the 25th Annual ACM Symposium on Theory of Computing, 1993, pp. 691-697.
- P. Klein, S. Plotkin, S. Rao and E. Tardos: Approximation Algorithms for Steiner and Directed Multicuts.
- Zoya Svitkina, and Eva Tardos. Min-Max Multiway Cut. Proceedings of APPROX 2004.
Separating cutting planes
- L. Fleischer and E. Tardos: Separating Maximally Violated Comb Inequalities in Planar Graphs, tech report version of the paper in the Proceedings of the 5th International Integer Programming and Combinatorial Optimization Conference (IPCO), June 1996, pp. 475-489.
Other Miscellaneous papers
- E. Tardos: The Gap Between Monotone and Non-Monotone Circuit Complexity is Exponential. Combinatorica, 1987, 7(4) 141-142.
402 Gates Hall
eva.tardos@cornell.edu
607/255-0984
Departments and programs
Links
Keywords
Algorithm design and algorithmic game theory
Edward Swartz
Professor
Publications
- Projection volumes of hyperplane arrangements (with C. Klivans), Discrete and Computational Geometry, 46 (2011), 417-426.
- Socles of Buchsbaum modules (with I. Novik), complexes and posets Adv. in Math., 222 (2009), 2059-2084.
- Face enumeration: from spheres to manifolds, J. Europ. Math. Soc., 11 (2009), 449-485.
- Topological representations of matroids, J. Amer. Math. Soc., 16(2003), 427-442.
- Matroids and quotients of spheres, Math. Zeit., 241 (2002), 247-269.
592 Malott Hall
ebs22@cornell.edu
Education
- B.A. (Mathematics), University of Rochester, Rochester, NY, 1981.
- M.S. (Mathematics), Yale University, New Haven, CT, 1989.
- Ph.D. (Mathematics), University of Maryland, College Park, MD, 1999.
Departments and programs
Links
Karola Mészáros
Associate Professor
Publications
- Schubert polynomials as integer point transforms of generalized permutahedra (with Alex Fink and Avery St. Dizier) Advances in Mathematics, accepted. http://arxiv.org/abs/1706.04935
- From generalized permutahedra to Grothendieck polynomials via flow polytopes (with Avery St. Dizier) preprint. http://arxiv.org/abs/1705.02418
- The polytope of Tesler matrices (with A. H. Morales and B. Rhoades), Selecta Mathematica, to appear. http://arxiv.org/abs/1409.8566
- Toric matrix Schubert varieties and their polytopes (with L. Escobar), Proceedings of the American Mathematical Society, to appear. http://arxiv.org/abs/1508.03445
- Subword complexes via triangulations of root polytopes (with L. Escobar), preprint. http://arxiv.org/abs/1502.03997
- Product formulas for volumes of flow polytopes, Proceedings of the American Mathematical Society 143 no. 3, (2015), 937-954.
- Flow polytopes of signed graphs and the Kostant partition function (with A. H. Morales), International Mathematical Research Notices no. 3, (2015), 830-871.
- Root polytopes, triangulations, and the subdivision algebra, II, Transactions of the American Mathematical Society 363 no. 11, (2011), 6111-6141.
- Root polytopes, triangulations, and the subdivision algebra, I, Transactions of the American Mathematical Society 363 no 8, (2011), 4359-4382.
435 Malott Hall
km626@cornell.edu
Education
- Ph.D. (2010) Massachusetts Institute of Technology
Departments and programs
Links
Lionel Levine
Professor
Publications
- Formation of large-scale random structure by competitive erosion (with S. Ganguly and S. Sarkar), Annals of Probability, to appear.
- Sandpiles on the square lattice (with B. Hough and D. C. Jerison), Communications in Mathematical Physics (2019) 367:33--87
- The Apollonian structure of integer superharmonic matrices (with W. Pegden and C. Smart), Annals of Mathematics (2017) 186:1--67
- Apollonian structure in the abelian sandpile (with Wesley Pegden and Charles K. Smart), Geometric and Functional Analysis 26 (2016), no. 1, 306-336.
- Threshold state and a conjecture of Poghosyan, Poghosyan, Priezzhev and Ruelle, Communications in Mathematical Physics 335 no. 2 (2015), 1003–1017.
- Internal DLA and the Gaussian free field (with D. Jerison and S. Sheffield), Duke Mathematical Journal 163 no. 2 (2014), 267–308.
- Equations solvable by radicals in a uniquely divisible group (with C.J. Hillar and D. Rhea), Bulletin of the London Mathematical Society 45 (2013), 61–79.
- Logarithmic fluctuations for internal DLA (with D. Jerison and S. Sheffield), Journal of the American Mathematical Society 25 (2012), 271–301.
- Parallel chip-firing on the complete graph: devil's staircase and Poincaré rotation number, Ergodic Theory and Dynamical Systems 31 (2011), 891–910.
- Driving sandpiles to criticality and beyond (with A. Fey and D. B. Wilson), Physical Review Letters 104 (2010), 145703.
438 Malott Hall
levine@math.cornell.edu
Education
- Ph.D. (2007) University of California at Berkeley
Departments and programs
Links
Allen Knutson
Professor
Publications
- Complete moduli spaces of branchvarieties (with Valery Alexeev), Crelle's Journal (to appear).
- Four positive formulae for type A quiver polynomials (with Ezra Miller and Mark Shimozono), Inventiones Mathematicae 166 (2006), no. 2.
- Gröbner geometry of Schubert polynomials (with Ezra Miller), Annals of Mathematics 161 (2005), 1245–1318.
- Puzzles and (equivariant) cohomology of Grassmannians (with Terence Tao), Duke Math. J. 119 (2003), no. 2, 221–260.
- The honeycomb model of GL(n) tensor products I: proof of the saturation conjecture (with Terence Tao), Journal of the AMS 12(1999), no. 4, 1055–1090.
515 Malott Hall
allenk@math.cornell.edu
Education
- Ph.D. (1996) Massachusetts Institute of Technology
Departments and programs
Links
Robert Kleinberg
Associate Professor
317 Gates Hall
robert.kleinberg@cornell.edu
607/255-9200
Departments and programs
Links
Keywords
Algorithms and theoretical computer science, especially economic aspects of algorithms, online learning and its applications, random processes in networks.
Jon M. Kleinberg
Tisch University Professor of Computer Science and Information Science and Interim Dean of Computing and Information Science
Publications
- Networks, Crowds, and Markets: Reasoning About a Highly Connected World (with D. Easley), Cambridge University Press, (2010).
- Algorithm Design (with E. Tardos). Addison Wesley, (2005).
318 Gates Hall
kleinber@cs.cornell.edu
Departments and programs
Links
Keywords
Networks and information
Tara Holm
Professor
Publications
- The topology of toric origami manifolds (with Ana Rita Pires), Math. Research Letters, 20 no. 5 (2013), 885–906.
- Orbifold cohomology of torus quotients (with Rebecca Goldin and Allen Knutson), Duke Math. J. 139 no. 1 (2007), 89–139.
- Computation of generalized equivariant cohomologies of Kac-Moody flag varieties (with Megumi Harada and Andre Henriques), Adv. in Math. 197 no. 1 (2005), 198–221.
- Conjugation spaces (with Jean-Claude Hausmann and Volker Puppe), Algebr. Geom. Topol. 5 (2005), 923–964.
- Distinguishing chambers of the moment polytope (with Rebecca Goldin and Lisa Jeffrey), J. Symp. Geom. 2 no. 1 (2003), 109–131.
320 Malott Hall
tara.holm@cornell.edu
607/2559928
Education
- Ph.D. (2002) Massachusetts Institute of Technology
Departments and programs
Links
Robert Connelly
Professor
Publications
- Straightening polygonal arcs and convexifying polygonal cycles (with E. Demaine and G. Rote), in preparation.
- The Kneser-Poulsen conjecture for spherical polytopes (with K. Bezdek), submitted.
- The Kneser-Poulsen conjecture (with K. Bezdek), Crelle's Journal, J. reine angew. Math. 553 (2002), 221–236.
- Tensegrity structures: Why are they stable?; in Rigidity Theory and Applications (M.F. Thorpe and P.M. Duxbury, eds.), Kluwer Academic/Plenum (1999), pp. 47–54.
- Mathematics and tensegrity (with A. Back), American Scientist March-April (1998), 142–151.
565 Malott Hall
rc46@cornell.edu
607/255-4301
Education
- Ph.D. (1969) University of Michigan