The professors Hemaspaandra
(Lane of URCS, left;
Edith of RIT-CS, right), on their 41st Adirondack mountaintop,
demonstrating the power of nonunary encodings
Lane A. Hemaspaandra
Note: Pre-marriage name = Lane A. Hemachandra.
Computer Science Department
University of Rochester
Rochester, NY 14627-0226
Email: ID = lane DOMAIN = cs.rochester.edu
Phone +1-585-275-1203 Fax +1-585-273-4556
B.S. (summa cum laude),
Yale University, Computer Science and Mathematics & Physics, 1981.
Stanford University, Computer Science, 1982.
Cornell University, Computer Science, 1984.
Cornell University, Computer Science, 1987.
computational social choice theory, algorithms and complexity theory, and
algorithmic game theory.
SIGACT Distinguished Service Prize, 2013.
Edward Peck Curtis Award for Excellence in Undergraduate
Teaching (University of Rochester's university-wide
award for undergraduate teaching), 2012.
ACM Distinguished Scientist,
Friedrich Wilhelm Bessel Research Award, Alexander von Humboldt Foundation, 2006. ( Photo of Lane receiving the award from Humboldt Foundation president, Dr. Wolfgang Fruehwald, June, 2007.)
JSPS (Japan Society for the Promotion of Science) Invitational Fellow, 2005.
Bridging Fellow (Political Science), University of Rochester, 1994.
Presidential Young Investigator, 1989-1995.
Research Initiation Award, 1988-1990.
Fannie and John Hertz Foundation Fellowship, 1982-1987.
Ph.D.s and Postdocs Advised:
Lane and his wife Edith are
climbed the 46 major peaks of New York State's Adirondack Mountains.
Posters describing research done by the Lane and his students/collaborators:
Control in the Presence of Manipulators: Cooperative and Competitive Cases:
Schulze and Ranked-Pairs Voting Are
Fixed-Parameter Tractable to Bribe,
Manipulate, and Control:
Control Complexity of Schulze Voting:
Weighted Electoral Control:
The Complexity of Bribery in Elections: view it
Guarantees for the Success Frequency of an Algorithm
for Finding Dodgson-Election Winners: view it
Politics Good, Computation Bad
(by Chris Homan about our group's Power Index work): view it
One-Way Functions and Cryptography: view it
Rice-Style Theorems in Complexity Theory: view it
Here are two videos made by Lane for our graduate-student
A 12-minute video (in .m4v format) from 2010
case it below doesn't have the video ready to roll but rather says
that this video is not supported in your browser---I've tested it just on Safari and Firefox and it seems ok in both for me---here is the video as an
A 3-minute video (in .m4v format) from 2016 of Lane proving---very quickly as this was during a "2-Minute Madness" session in which each speaker got only 2 minutes in which to speak---a special case of a theorem from his 1989 Information and Computation paper with Jin-Yi Cai, namely, proving that if there is a polynomial-time function that given any Boolean formula outputs a list of two values one of which is its number of satisfying assignments, then #SAT itself is outright in polynomial time:
Your browser does not support the video tag.
slides from Lane's Talk on Lewis Carroll's 1876 Election System
presentation (powerpoint) made by Christopher Homan on his paper with Lane on Heuristics for Lewis Carroll's 1876 Election System
presentation made by Christopher Homan about the paper
"Power Balance and Apportionment Algorithms for the United States Congress,"
L. Hemaspaandra, K. Rajasethupathy,
P. Sethupathy, and M. Zimand,
ACM Journal of Experimental Algorithmics,
#1, August 1998.
TheoryCanal: The Rochester-Area Theory Seminar Series
Theoretical Computer Science Research at URCS
A wonderful picture, taken by Yuan Sun in October 2002, of the waterfalls and leaves at
Letchworth State Park near Rochester.
My student Mayur Thakur's March 15, 2004 Hour-Long Job Talk at University of Missouri at Rolla, Where He Became an Assistant Professor (Warnings: This is a .rm video, and seems to (on my mac) only work if one has RealOne Player and puts it into Theatre or Full-Screen mode; otherwise one doesn't seem to get the
picture at all. Also, though the sound starts right away, the
picture of Mayur starts only 66 seconds into this one hour video.)
Carlson Library CS Resources Page
Numbers Are Magic and Fun
The Wisdom of Juris Hartmanis (from Upson's Familiar Quotations,
4th Ed.), pages:
3; special bonus: see
a great man and a statue
The Wisdom of John Hopcroft (from Upson's
Familiar Quotations, 4th Ed.).
The Wisdom of George Polya.
to URCS Faculty directory
to URCS Home Page
April 22, 2016.