Evdokia Nikolova



Assistant Professor
Department of Electrical and Computer Engineering
The University of Texas at Austin
1616 Guadalupe St., UTA 7.212 Austin, TX 78701
USA
Office: UTA Building, Room 7.212
Tel: 512-471-1932
Email: my last name@austin.utexas.edu

Research interests: Algorithms for risk mitigation in networks; Optimization under uncertainty; Algorithmic Game Theory and Mechanism Design.


News & Links


Short bio

Evdokia Nikolova is an Assistant Professor in the Department of Electrical and Computer Engineering at the University of Texas at Austin, where she is a member of the Wireless Networking & Communications Group. She graduated with a BA in Applied Mathematics with Economics from Harvard University, MS in Mathematics from Cambridge University, U.K. and Ph.D. in Computer Science from MIT.

Evdokia Nikolova's research aims to improve the design and efficiency of complex systems (such as networks and electronic markets), by integrating stochastic, dynamic and economic analysis. Her recent work examines how human risk aversion transforms traditional computational models and solutions. One of her algorithms has been adapted in the MIT CarTel project for traffic-aware routing. She currently focuses on developing algorithms for risk mitigation in networks, with applications to transportation and energy. She is a recipient of an NSF CAREER award.


Publications and Working Papers*

Asymptotically tight bounds for inefficiency in risk-averse selfish routing
Thanasis Lianeas, Evdokia Nikolova, Nicolas E. Stier Moses.
Working paper, July 2015.

Approximation Algorithms for Route Planning with Nonlinear Objectives. [arXiv]
Ger Yang and Evdokia Nikolova.
In Proceedings of the Thirtieth AAAI Conference on Artificial untelligence (AAAI'16). Phoenix, Arizona, February 12–17, 2016.

New Complexity Results and Algorithms for the Minimum Tollbooth Problem, [ArXiv]
Soumya Basu, Thanasis Lianeas, Evdokia Nikolova.
In proceedings of the 2015 Conference on Web and Internet Economics (WINE'15), Amsterdam, The Netherlands, December 9-12, 2015.

The Burden of Risk Aversion in Mean-Risk Selfish Routing [ArXiv]
Evdokia Nikolova, Nicolas E. Stier Moses.
In Proceedings of the Sixteenth ACM Conference on Economics and Computation (EC'15). Portland, OR, June 15-19, 2015.

Approximately Optimal Risk-averse Routing Policies via Adaptive Discretization. [pdf]
Darrell Hoy and Evdokia Nikolova.
In Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence (AAAI'15). Austin, TX, January 25-30, 2015.

A Mean-Risk Model for the Traffic Assignment Problem with Stochastic Travel Times [pdf]
Evdokia Nikolova, Nicolas E. Stier Moses.
Operations Research, 62:2, 366.382, 2014.
(a preliminary version titled ``Stochastic Selfish Routing" appeared in the SAGT conference and a short summary of the paper appeared in ACM SIGecon Exchanges, as listed below)

Risk Sensitivity of Price of Anarchy under Uncertainty. [pdf]
Georgios Piliouras, Evdokia Nikolova and Jeff S. Shamma.
In Proceedings of the 14th ACM Conference on Electronic Commerce (EC 2013). Philadelphia, Pennsylvania, June 16-20, 2013.

Sample complexity of risk-averse bandit-arm selection. [pdf]
Jia Yuan Yu, Evdokia Nikolova.
In Proceedings of the 23rd International Joint Conference on Artificial Intelligence (IJCAI 2013). Beijing, China, August 3-9, 2013.

Raven: Energy Aware QoS Control for DRNs.
H. Chenji, L. Smith, R. Stoleru, E. Nikolova.
In Proceedings of IEEE 9th International Conference on Wireless and Mobile Computing, Networking and Communications (WiMob), 2013.

Multi-modal Journey Planning in the Presence of Uncertainty. [pdf]
Adi Botea, Michele Berlingerio, Evdokia Nikolova.
In Proceedings of the 23rd International Conference on Automated Planning and Scheduling (ICAPS 2013). Rome, Italy, 10-14 June, 2013.

Practical Route Planning Under Delay Uncertainty: Stochastic Shortest Path Queries [pdf]
Sejoon Lim, Christian Sommer, Evdokia Nikolova, and Daniela Rus
In RSS - Robotics: Science and Systems VIII, 2012.

Stochastic Selfish Routing [pdf]
Evdokia Nikolova, Nicolas E. Stier Moses.
ACM SIGecom Exchanges, 11:1, 21-25, 2012.
(Summary of paper below.)

Stochastic Selfish Routing [pdf]
Evdokia Nikolova, Nicolas E. Stier Moses.
In Proceedings of the Fourth Symposium on Algorithmic Game Theory (SAGT '11), Salerno, Amalfi Coast, Italy, Lecture Notes in Computer Science, Springer, Berlin, 2011.

Approximation Algorithms for Offline Risk-averse Combinatorial Optimization
Evdokia Nikolova.
Full version: [pdf]
Conference: [pdf] (with title Approximation Algorithms for Reliable Stochastic Combinatorial Optimization.) In Proceedings of APPROX '10, Barcelona, Spain, 2010.

High-performance heuristics for optimization in stochastic traffic engineering problems [ps], [pdf]
Evdokia Nikolova.
In Proceedings of the Seventh International Conference on Large-Scale Scientific Computing (LSSC), 2009.

Offline Ad Slot Scheduling
Jon Feldman, S. Muthukrishnan, Evdokia Nikolova, Martin Pal.
Conference: [pdf] (with title A Truthful Mechanism for Offline Ad Slot Scheduling) In Proceedings of the First International Symposium on Algorithmic Game Theory (SAGT '08), Padeborn, Germany, May 2008.
Full version: [pdf]

Route Planning under Uncertainty: The Canadian Traveller Problem [ps], [pdf]
Evdokia Nikolova, David Karger.
In Proceedings of the Twenty-Third Conference on Artificial Intelligence (AAAI), Chicago, IL, July 2008.

On the Hardness and Smoothed Complexity of Quasi-Concave Minimization [ps], [pdf]
Jonathan Kelner, Evdokia Nikolova.
In Proceedings of FOCS '07, Providence, RI, October 2007.

Incentive-Compatible Interdomain Routing with Linear Utilities
Alexander Hall, Evdokia Nikolova, and Christos Papadimitriou.
Conference: [pdf] In Proceedings of the 3rd International Workshop On Internet And Network Economics (WINE 2007), LNCS 4858, Springer Verlag, San Diego, USA, pages 232-244, December 2007.
Journal: [pdf] Internet Mathematics. Volume 5, Number 4 (2008), 395-410. (Special Issue for Selected papers from WINE'07.)

A Strategic Model for Information Markets [ps], [pdf]
Evdokia Nikolova, Rahul Sami.
In Proceedings of Eighth ACM Conference on Electronic Commerce (EC '07), San Diego, CA, June 2007.

Betting on Permutations [ps], [pdf]
Yiling Chen, Lance Fortnow, Evdokia Nikolova, David Pennock.
In Proceedings of Eighth ACM Conference on Electronic Commerce (EC '07), San Diego, CA, June 2007.

Stochastic Shortest Paths via Quasi-Convex Maximization [ps], [pdf]
Evdokia Nikolova, Jonathan Kelner, Matthew Brand and Michael Mitzenmacher.
In Proceedings of 2006 European Symposium of Algorithms (ESA '06), Zurich, Sep 2006.

Optimal Route Planning under Uncertainty [ps], [pdf]
Evdokia Nikolova, Matthew Brand, and David Karger.
In Proceedings of 2006 International Conference on Automated Planning & Scheduling (ICAPS 2006), Lake District, England, June 2006.

VCG Overpayment in Random Graphs [ps], [pdf]
David Karger, Evdokia Nikolova.
Brief Announcement in PODC 2005, Las Vegas, July '05. [ps], [pdf]
Conference on Decision and Control (CDC '06), San Diego, CA, December '06. [ps], [pdf]
DIMACS Workshop on Computational Issues in Auction Design, October 2004, Rutgers University.

First-Price Procurement Auctions
Nicole Immorlica, David Karger, Evdokia Nikolova, and Rahul Sami. First-Price Path Auctions.
Conference: [pdf] (with title First-Price Path Auctions) In Proceedings of Sixth ACM Conference on Electronic Commerce (EC '05), Vancouver, June 2005.
Full version: [pdf]

Surveys

Combinatorial Betting [ps], [pdf]
Yiling Chen, Lance Fortnow, Evdokia Nikolova, David Pennock.
To appear in Proceedings of SIGecom Exchanges special issue on combinatorial auctions.

Theses

Strategic Algorithms. [pdf]
Evdokia Nikolova.
Ph.D. Thesis, Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2009.

Duality of the Gradient Method and Lyapunov Functions in the context of Congestion Control. [ps] [pdf]
Evdokia Nikolova.
Math Tripos Essay, Cambridge University, 2003.

*Small Print
The documents distributed here have been provided as a means to ensure timely dissemination of scholarly and technical work on a noncommercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.


Teaching

Fall 2015: Mechanism Design for the Smart Grid, Simons Institute, Berkeley, CA
Spring 2015: EE 381V: Advanced algorithms. Course materials on Canvas. Syllabus
Fall 2014: EE 360C: Algorithms. Course materials on Canvas.
Spring 2014: EE 381V: Game Theory. Course materials on Blackboard.

Courses taught at Texas A&M University:
Fall 2013: CSCE 489/689: Special Topics in Algorithmic Game Theory (Syllabus pdf)
Spring 2013: CSCE 411H: Design and Analysis of Algorithms
Fall 2012: CSCE 629: Analysis of Algorithms
Spring 2012: CSCE 689: Special Topics in Algorithmic Game Theory (Syllabus pdf)
Fall 2011: CSCE 689: Special Topics in Stochastic and Risk-averse Optimization (Syllabus pdf)



Service

Program Committees: WINE 2015, EC 2014, EC 2013, AAAI 2013, EC 2012, WWW 2012, EC 2010.

Workshop Organizer: Invited Session Chair: ISMP 2015, ISMP 2012, ISMP 2009.

Outreach: Speaker at Camp Texas (for incoming UT freshmen), Camp Balcones Springs, Texas, August 17, 2014; August 18, 2015.



Funding

I gratefully acknowledge the following grants whose financial support makes my research possible:


Dr. Butt's Orthodontics Somerville Orthodontics Somerville Orthodontist Somerville Massachusetts Orthodontist Dr. Butts Orthodontics Marshfield Orthodontics Marshfield Orthodontist Marshfield Orthodontist, Massachusetts Dr. M H Butt Dr. Hanif Butt Boston Orthodontist Boston Orthodontics Cambridge Orthodontist Cambridge Orthodontics Yarmouth Orthodontist Yarmouth Orthodontics Yarmouth Orthodontics, Massachusetts Harvard trained Orthodontist Dr. M. Hanif Butt Harvard graduated Orthodontist Dr. M. Hanif Butt