Matthew Paul Johnson

Education

CUNY Graduate Center. New York, NY, 2005-present
Ph.D. in Computer Science, GPA: 4.00

• Received a prestigious CUNY Science Fellowship.
• Scored 99.75/100 (average score: 67/100) on Qualifying Exam (rank: 1 out of 25).
• Coursework: Optimization, Topics in Complexity (NYU), Combinatorics, Tournament Ranking Project.

Columbia University. New York, NY 1998-2002
M.S. in Computer Science, GPA: 3.73

• Received a fully funded MS-TA-ship.
• Coursework: Machine Learning, Crypto, Mathematical Logic, Computational Genomics.

Columbia University. New York, NY 1998-2002
B.S. in Computer Science

• Coursework: Information Theory, Graph Theory, Set Theory, Modern Geometry, AI, Philosophy of Math.

Lawrence University. Appleton, WI, 1995-1998
B.A. double major in Math and Philosophy

• Coursework: Foundations of Algebra, Real Analysis, Philosophy of Mind.

Research

Sensor Assignment. at CUNY GC/IBM/ITA with Prof. Amotz Bar-Noy

• Modeled the problem of optimally assigning multiple sensors to multiple missions in terms of weighted bipartite semi-matching and maximum flows.
• Proved that certain problem variants are strongly NP-Hard and APX-Hard.
• Found and implemented (in Java) efficient heuristic-based algorithms, including naive greedy algorithms, LP-rounding, and distributed bidding algorithms.
• Currently seeking efficient algorithms with provable approximation ratios.

Energy Demand-Smoothing. at CUNY GC/CISDD/Gaia with Prof. Amotz Bar-Noy

• Studied the online problem of smoothing peaks in energy demand curves, by storing surplus energy in a battery.
• Adapted the optimal offline algorithm to the online setting, producing a simple linear-time online algorithm with excellent empirical performance.
• Currently adapting an existing controller system (written in C) into a simulation engine for testing algorithms on historical data.

Computational Finance. at Columbia with Dr. German Creamer

• Studied constant rebalanced portfolios and the underlying information theory.
• Implemented Cover's Universal Portfolio algorithm.

Genetic Algorithms. at Columbia with Prof. Andrew Kosoresow

• Applied genetic algorithms (GAs) to the empirically analysis of algorithms, including NP-Complete problems and online algorithms.
• Developed a GA that finds worst-case instances of optimization problem instances.
• Confirmed a conjectured bound on a competitive algorithm for the Taxi Cab Problem.

Teaching

City College of New York. CS Department, New York, NY, Spring 2005-Present
Adjunct Lecturer

• Intro to Programming & Computer Science, Fall 2005 & Fall 2006
• Data Structures, Spring 2005

NYU Stern School of Business. IS Department, New York, NY, Spring 2004-Spring 2006
Adjunct Assistant Professor

• Database Management Systems, Spring 2004, Spring 2005, Spring 2006

CUNY Institute for Software Development & Design. New York, NY, 2004-2005
Instructor

• Oracle 10g: SQL & PL/SQL: October 2004, January 2005, June 2005, September 2005

Columbia University. CS Department, New York, NY, 2002-2004
Instructor

• Programming Languages. C++, Spring & Fall 2003
• Data Structures and Algorithms, Summer 2004
• Programming Languages: C, Spring & Fall 2003
• Discrete Math, Summer 2003
• Intro to Computer Programming in Java, Spring 2003
• Intro to Computer Programming in C, Fall 2002
• Introduction to Computational Complexity (CVN), Spring 2002-Fall 2003

Industry Experience

Information Builders. New York, NY, May, 2002-January, 2004
Software Developer, WebFocus Division

• Analyzed SSH and S/MIME security protocols, and implemented load-balancing in the project's job-handling server.
• Technologies: Java, JDBC, SQLServer, BouncyCastle, Ant, Eclipse, SourceSafe.

Random Walk Computing. New York, NY, February, 2001-March, 2002
Associate Consultant

• In a team of five, developed a Lehman Brothers trading system, which supported various financial instruments.
• Technologies: Java, XML, Oracle, JMS, TIB/Rendezvous, FIX, cvs, Ant, JUnit.

Konsult, Inc.. Oshkosh, WI, June, 1995-December, 2000
Programmer

• Lead developer for the first Windows version of the AADR expert system.

Publications

Conference Papers.

• "A Survey of Sensor Selection Schemes in Wireless Sensor Networks" (with Hosam Rowaihy, Sharanya Eswaran, Amotz Bar-Noy, Alun Preece, Ted Brown, Dinesh Verma, Tom La Porta). SPIE Unattended Ground, Sea, and Air Sensor Technologies and Applications IX, Orlando, FL. To appear.
• "Finding Worst-Case Instances of, and Lower Bounds for, Online Algorithms Using Genetic Algorithms" (with Andrew P. Kosoresow) in AI 2002: Advances in Artificial Intelligence: 15th Australian Joint Conference on Artificial Intelligence, Proceedings. LNAI 2557. Springer Verlag, 2002.
• "Finding Worst-Case Instances, and Lower Bounds, for NP-Complete Problems Using Genetic Algorithms" (with Andrew P. Kosoresow) in Proceedings of the 4th Asia-Pacific Conference on Simulated Evolution And Learning. 2002.

Technical Reports.

• "A Survey of Sensor Selection Schemes in Wireless Sensor Networks" (with Hosam Rowaihy, Sharanya Eswaran, Dinesh Verma, Amotz Bar-Noy, Theodore Brown, & Thomas La Porta). PSU NSRC Tech Report NAS-TR-0055-2006.
• "Geometric Considerations for Distribution of Sensors in Ad-hoc Sensor Networks" (with Ted Brown, Deniz Sarioz, Amotz Bar-Noy, Tom LaPorta, Dinesh Verma, & Hosam Rowaihy). CUNY CS Tech Report TR-2006014.

Presentation.

• "Demand Smoothing Through Energy Buffering" (with Amotz Bar-Noy, Ted Brown & Ib Olson) at the CUNY Sustainability Conference, CUNY Grad Center, 12/8/06.

Book Chapter.

• "Lower Bounds via Worst-Case Instances via Genetic Algorithms" (with Andrew P. Kosoresow) in Recent Advances in Simulated Evolution and Learning, Kay Chen Tan, et al. eds. World Scientific series on Advances in Natural Computation. 2004.

References

Amotz Bar-Noy. of CUNY; amotz@sci.brooklyn.cuny.edu

German Creamer. of Columbia and American Express; gcreamer@cs.columbia.edu