Resume

Name :         MohammadTaghi Hajiaghayi
Personal Information:
                       Birth year: 1979
Office :         Room. 2-088, Dept. of Mathematics, MIT
                       Room 32-G596, MIT CSAIL, Phone (617) 253-6182
Residence:   550 Memorial Dr. Apt 21E-3
                        Cambridge, MA 02139, USA
                        Phone : (617) 225-1257
Email : hajiagha@theory.lcs.mit.edu (Permanent Email)
               hajiagha@mit.edu
               hajiaghayi@yahoo.com
Homepage : http://www.mit.edu/~hajiagha
Current Position : Ph.D. Candidate, Applied Mathematics and Computer Science Program, MASSACHUSETTS INSTITUTE OF TECHNOLOGY
Education :
          Sep 1997- Sep 2000 B.Sc. in Computer Engineering, Sharif University of Technology,   Tehran, Iran.
                   GPA : 18.76 out of 20.00
                   Rank in class : 1.
                   B.S Project : Pseudo-Matching and Multicasting.
                  Advisor : Dr. M. Ghodsi
                                  Relevant courses work: Advanced Graph Algorithms, Digital Design, Formal Language and Automata Theory, Parallel Algorithms, Computational Complexity Theory, Artificial Intelligence, Compilers, O/S, networking, Databases and Combinatorics.
           Sep 2000- Sep 2001 M.Sc in Computer Science, University of Waterloo, Ontario, Canada.
                                GPA : 5.0 out of 5.0
                                M.S Project : Algorithms for Graphs of (Locally) Bounded Treewidth
                                Supervisor : Prof. N. Nishimura
                                  Relevant courses work:

Advanced Algorithms

Combinatorial Optimization

Computational Complexity Theory

Topics in Software Design, Concentrating on Software Architecture

Advanced Topics in Databases: Text-Dominated Databases

             Sep 2001- Present Ph.D. Candidate in Applied Mathematics, joint with Theory of Computation Group in Laboratory for Computer Science, M.I.T.
             GPA : 5.0 out of 5.0.
             Supervisors: Prof. Erik D. Demaine and Prof. Tom Leighton
                                  Relevant courses work:

Adv Topics: Computer Graphics
Distributed Algorithms
Advanced Algorithms
Seminar in Combinatorics
Advanced complexity theory
Geometric Computation
Spec Topics in Mathematics: Internet Research Problems
Spec Seminar in Operations Research: Theory of Scheduling
Spec Topics in Computer Sciences: Algorithms for Massive Data Sets

Randomized Algorithms
Research in Mathematics: Embedding into norm spaces
Random Walks and Polynomial-Time Algorithms (listener)
Spec Topics in Computer Sciences: Essential coding theory (listener)
Advanced Distributed Algorithms (listener)
Topics in Combinatorial Optimization (listener)
Electronic Market Design (listener)
Microeconomic Theory (listener)

Publications :

Journal Articles:

17 Hajiaghayi, M.T.; Demaine, E.D.; Fomin, F.V.;Thilikos, D.;
Fixed-Parameter Algorithms for the (k,r)-Center in Planar Graphs and Map Graphs,
ACM Transactions on Algorithms. To appear. (Initially accepted to Journal of Algorithms, but it is moved to TALG to support the move.) A preliminary version appeared in 30th International Colloquium on Automata, Languages and Programming (ICALP), July, 2003, pp. 829-844.

16 Hajiaghayi, M.T.; Demaine, E.D.; Thilikos, D.;
Exponential Speedup of Fixed Parameter Algorithms on K_{3,3}-minor-free or K_5-minor-free Graphs,
Algorithmica, To appear. A preliminary version appeared in Annual International Symposium on Algorithms and Computation, November, 2002.

15 Hajiaghayi, M. T.; Bahramgiri, M.; Mirrokni, V. S.;

Fault-tolerant and 3-Dimensional Distributed Topology Control Algorithms in Wireless Multi-hop Networks,
ACM/Kluwer Wireless Networks. To appear. A preliminary version appeared in the 11th IEEE International Conference on Computer Communications and Networks, October, 2002, pp. 392-398.

14 Hajiaghayi, M.T.; Demaine, E.D.; Fomin, F.V.;Thilikos, D.;

Bidimensional Parameters and Local Treewidth,
Siam Journal on Discrete Mathematics. To appear. Preliminary versions appeared in Latin American Theoretical Informatics, April, 2004 and Annual European Symposium on Algorithms, September, 2003.

13 Hajiaghayi, M.T; Biedl, T; Chan. T; Ganjali, Y; Wood, D.R.;

Balanced vertex-orderings of graphs,
Discrete Applied Mathematics. To appear.

12 Hajiaghayi, M. T.; Ganjali Y.;

Characterization of Networks Supporting Multi-dimensional Linear Interval Routing Schemes
Theoretical Computer Science, Vol 326, No. 1-3, pp. 103-116.

11 Hajiaghayi,M.T.; Demaine, E.D.;

Diameter and Treewidth in Minor-Closed Graph Families, Revisited,
Algorithmica. Vol 40, No. 3, pp. 211-215, 2004.

10 Hajiaghayi, M.T.; Demaine, E.D.; Nishimura, N; Ragde, P; Thilikos, D.;

Approximation algorithms for classes of graphs excluding single-crossing graphs as minors
Journal of Computer and System Sciences, Vol 69, No. 2, pp. 166-195, 2004.

9 Hajiaghayi, M. T.; Coppersmith, D.; Gamarnik, D.; Sorkin, G. B.;

Random MAX SAT, Random MAX CUT, and Their Phase Transitions
A special issue of Random Structures and Algorithms, Vol 24, Issue 4 , pp. 502-545. A preliminary version appeared in Proceedings of Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 364-373, January 12-14, 2003, Baltimore.

8 Hajiaghayi, M.T.; Hajiaghayi, M.;

On the bounded fragmentation property and its applications,

European Journal of Combinatorics, Vol 24, No. 7, pp. 891-896, 2003. A preliminary version appeared in Proc. Euroconference on Combinatorics, Graph Theory and Applications, EuroCOMB'03, Sep. 2003.

7 Hajiaghayi, M. T.; Mahdian, M.; Mirrokni, V.S.;

The facility location problem with general cost functions,
Networks, Vol. 42, No. 1, pp. 42-47, 2003.

6 Hajiaghayi, M.T.; Biedl, T.; Buss, J.F.; Demaine, E.D., Demaine, M.L.; Vinar,T.;

Palindrome Recognition Using a Multidimensioinal Tape,
Theoretical Computer science, Vol. 302, No. 1-3, pp. 475-480, 2003.

5 Hajiaghai¹, M.T.; Veloso, M.; Balch, T.; Stone, P.; Kitano, H.; Yamasaki, F.; Endo, K.; Asada, M; Jamzad, M; Sadjad, B. S.; Mirrokni, V. S.; Kazemi, M.; Chitsaz, H.; Heydarnoori, A.; Chiniforooshan E.;

RoboCup-2001 -The Fifth Robotic Soccer World Chapmpionships.
AI magazine, Vol. 23, No. 1, pp. 55-68, 2002.

4 Hajiaghayi, M.T.; Ghodsi, M; Mahdian, M.; Mirrokni, V.S.;

Path-matching in graphs with length constraints,
Networks, Vol 39, No. 4, pp. 210-215, 2002.

3 Hajiaghayi, M.T.; Ganjali Y.;

A Note on the Consecutive Ones Submatrix Problem,
Information Processing Letters, Vol 83, No. 3, pp. 163-166, 2002.

2 Hajiaghayi, M.T; Nishimura, N; Ragde, P; Thilikos, D.;

Fast approximation schemes for K_{3,3}-minor-free or K_{5}-minor-free graphs,

Electronic Notes in Discrete Mathematics Vol 10, 2001. A preliminary version appeared in Proc. Euroconference on Combinatorics, Graph Theory and Applications, EuroCOMB'01, Sep. 2001: 158-163.

1 Hajiaghaee¹, M. T.; Mahmoodian, E. S.; Mirrokni, V. S.; Saberi, A.; Tusserkani;

On the simultaneous edge-coloring conjecture,
Discrete Mathematics 216 (2000), no. 1-3, 267--272.

Conference and Submitted Papers (excluding those that have already appeared in journals)

28 M.T. Hajiaghayi; H. Raecke;

An O(sqrt{n})-Approximation Algorithm For Directed Sparsest Cut, Submitted.

27 M.T. Hajiaghayi; K. Jain; K. Konwar; L.C. Lau; I.I. Mandoiu; A. Russell; A. Shvartsman; V.V. Vazirani;

The Minimum k-Colored Subgraph Problem in Haplotyping and DNA Primer Selection, Submitted.

26 J.L. Bredin; E.D. Demaine; M.T. Hajiaghayi; D. Rus;

Deploying Sensor Nets with Guaranteed Capacity and Fault Tolerance, Submitted to INFOCOM 2005.

25 M.T. Hajiaghayi; L.E. Li; V.S. Mirrokni; M. Thottan;

Bandwidth Sharing VPN Network Design for Multi-class Traffic with Application to VoIP, Submitted to INFOCOM 2005.

24 M.T. Hajiaghayi; R.D. Kleinberg; M. Mahdian; D.C. Parkes;

Online Auctions with Re-usable Goods, Submitted.

23 Mohammad T. Hajiaghayi; Jeong H. Kim;

Tight Bounds For Random MAX 2-SAT, Submitted.

22 Jain, K.; Hajiaghayi, M.T.;

The Prize-Collecting Generalized Steiner Tree Problem via a new approach of Primal-Dual Schema, Submitted.

21 Jain, K.; Hajiaghayi, M.T.; Talwar, K.;

The Generalized Deadlock Resolution Problem, Submitted.

20 E.D. Demaine; M.T. Hajiaghayi;

Quickly Deciding Minor-Closed Parameters in General Graphs, Submitted to European Journal of Combinatorics, 2004.

19 Hajiaghayi, M.T.; Leighton, F.T.;

On the max-flow min-cut ratio for directed multicommodity flows,
Submitted to Theoretical Computer science, 2003. See Tech. Report MIT-LCS-TR-910.

18 E.D. Demaine; M.T. Hajiaghayi;

Fast Algorithms for Hard Graph Problems: Bidimensionality, Minors, and Local Treewid,
Invited presentation in the 12th International Symposium on Graph Drawing(GD), 2004, New York City, 2004. This paper surveys our theory of bidimensionality and its known combinatorial and algorithmic results of this theory.

17 E.D. Demaine; M.T. Hajiaghayi;

Graphs Excluding a Fixed Minor have Grids as Large as Treewidth, with Combinatorial and Algorithmic Applications through Bidimensionality (full paper),
in Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Vancouver, British Columbia, Canada, January 23-25, 2005, To appear. Journal version submitted to Combinatorica.

16 E.D. Demaine; M.T. Hajiaghayi;

Bidimensionality: New Connections between FPT Algorithms and PTASs (full paper),
in Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Vancouver, British Columbia, Canada, January 23-25, 2005, To appear.

15 N. Alon; M. Badoiu; E.D. Demaine; M. Farach-Colton; M.T. Hajiaghayi; A. Sidiropoulos;

Ordinal Embeddings of Minimum Relaxation: General Properties, Trees, and Ultrametrics (full paper),
in Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Vancouver, British Columbia, Canada, January 23-25, 2005, To appear.
Journal version to be submitted to Siam Journal on Computing.

14 M.T. Hajiaghayi;Robert D. Kleinberg; Tom Leighton; Harald Raecke;

Oblivious Routing on Node-Capacitated and Directed Graphs (full paper),
in Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Vancouver, British Columbia, Canada, January 23-25, 2005, To appear.

13 B. Awerbuch; M.T. Hajiaghayi; R.D. Kleinberg; T. Leighton;

Online Client-Server Load Balancing Without Global Information (full paper),
in Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Vancouver, British Columbia, Canada, January 23-25, 2005, To appear.
Journal version to be submitted to Siam Journal on Computing.

12 Hajiaghayi, M.T.; Badoiu, M; Demaine, E.D.; Indyk, P.;

Low Dimensional Embedding with Extra Information,
To appear in the 20th ACM Symposium on Computational Geometry (SoCG), June 9 - 11, 2004, New York.
Journal version invited to Discrete & Computational Geometry for a special issue of selected papers from SoCG 2004.

11 Hajiaghayi, M.T.; Kleinberg, R.; Parkes, D.C.;

Adaptive Limited-Supply Online Auctions (full paper),
Proc. ACM Conference on Electronic Commerce (EC), pp. 71-80, May 17-20, 2004. New York.

10 Hajiaghayi, M.T.; Demaine, E.D.; Thilikos, D.;

The Bidimensional Theory of Bounded-Genus Graphs,
Proc. the 29th International Symposium on Math. Foundations of Computer Science, 2004, Prague, Europe, 2004. pp. 191-203. Journal version submitted to Siam Journal on Discrete Mathematics.

9 Hajiaghayi, M.T.; Demaine, E.D.;

Equivalence of Local Treewidth and Linear Local Treewidth and its Algorithmic Applications (full paper),
Proc. the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 840-849, January 11-13, 2004, New Orleans. See Tech. Report MIT-LCS-TR-903 for a more complete version.

8 Hajiaghayi, M.T.; Demaine, E.D.; Fomin, F.V.;Thilikos, D.;

Subexponential Parameterized Algorithms on Graphs of Bounded Genus and H-minor-free Graphs (full paper),
Proc. the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 830-839, January 11-13, 2004, New Orleans. See Tech. Report MIT-LCS-TR-905 for a more complete version. Journal version submitted to Journal of the ACM.

7 Hajiaghayi, M.; Immorlica, N.; Mirrokni, V.S.;

Power Optimization in Fault-Tolerant Topology Control Algorithms for Wireless Multi-hop Networks,

Proceedings of the Ninth Annual International Conference on Mobile Computing and Networking (MOBICOM), pp. 300-312, September 15-18 2003, San Diego. Journal version submitted to Siam Journal on Computing.

6 Hajiaghayi, M.T.; Sorkin G.B.;

The Satisfiability Threshold of Random 3-SAT Is at Least 3.52,
arXiv:math.CO/0310193 v2 22 Oct 2003. See also IBM Research Report RC22942, 2003.

5 Hajiaghayi, M.T.; Demaine, E.D.; Thilikos, D.;

1.5-Approximation for Treewidth of Graphs Excluding a Graph with One Crossing as a Minor,
Proc. the 5th International Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX), September 17-21, 2002, Italy, Lecture Notes in Computer Science 2462, pp. 67-80, 2002.

4 Hajiaghayi, M.T; Nishimura, N.;

Subgraph Isomorphism, log-Bounded Fragmentation and Graphs of (Locally) Bounded Treewidth,
Proc. the 27th International Symposium on Mathematical Foundations of Computer Science (MFCS), August 26-30, 2002, Poland, Lecture Notes in Computer Science 2420, pp. 305-318, 2002. Journal version submitted to Journal of Computer and System Sciences.

3 Hajiaghayi, M.T; Jamzad, M.;

Simple, fast, and robust self-localization in environments similar to the robocup environment,
Proc. the 18th International Conference on CAD/CAM, Robotics and Factories of the future (CARS&FOF), Porto, Portugal, vol (2), pp:513-522, 2002. Journal version submitted.

2 Hajiaghai¹, M.T.; Jamzad, M; Sadjad, B. S.; Mirrokni, V. S.; Kazemi, M.; Chitsaz, H.; Heydarnoori, A.; Chiniforooshan E.;

A Fast Vision System for Middle Size Robots in RoboCup,
The RoboCup 2001 International Symposium, winner of The Best Engineering Challenge Award, Lecture Notes in Computer Science 2377, pp. 71-80, 2002.

1 Hadji Aaghai¹, T; Jamzad, M.; Foroughnassiraei, A.; Mirrokni, V.S.; Ghorbani, R.; Heydar Noori, A.; Kazemi, M.; Chitsaz, H.; Mobasser, F.; Ebraahimi M.; Gudarzi, M; Ghaffarzadeganet. N.;

A Goal Keeper for Middle Size RoboCup,
RoboCup 2000, Lecture Notes in Computer Science 2019, 2001: 583-586.

Thesis

Hajiaghayi, M.T.;

Algorithms for Graphs of (Locally) Bounded Treewidth,
M.Sc. Thesis, Department of Computer Science, University of Waterloo, Waterloo, Ontario, Canada, September 2001.

Content of the thesis appeared in Journal papers [8], [10] (partially), and Conference paper [4].

Hajiaghayi, M.T.;

Multicasting and Pseudomatching (in Persian),
B.Sc. Thesis, Department of Computer Engineering, Sharif University of Technology, Tehran, Iran, September 2000

Content of the thesis appeared in Journal paper [4].

Book
Iranian Informatics Olympiad (in Persion) shared with V.S. Mirrokni and Y. Ahmadi, Young Scholars Club Pub. Sept, 2000.

Professional Activities:
I have reviewed manuscripts for the following journals and conferences:

Journal of the ACM, SIAM Journal on Computing, Theoretical Computer Science, ACM Transactions on Sensor Networks, The Australasian Journal of Combinatorics, Symposium on Foundations of Computer Science (FOCS), ACM Symposium on Computational Geometry (SoCG), ACM-SIAM Symposium on Discrete Algorithms (SODA), The IEEE Conference on Computer Communications (INFOCOM), Workshop on Graph Theoretic Concepts in Computer Science (WG), Workshop on Algorithm Engineering and Experimentation (ALENEX).

Awards/Honours :

Maximum number of accepted papers in SODA 2005 (five long papers). Tie with the maximum number from previous years due to Erik D. Demaine (SODA 2004), Uri Zwick (SODA 2002) and S. Muthukrishnan (SODA 2002).
Winner of the best Engineering Challenge Award in Robocup, 2001.
Third rank in the Middle Size League in World RoboCup Championship 2000 in Melbourne (see http://www.robocup2000.org).
First rank in the Middle Size League in European RoboCup Championship 2000 in Amsterdam (see http://www.robocup.nl).
Awarded the best undergraduate prize of Sharif University of Technology (Computer Eng. Dep.) in 2000 for the First who has finished his B.S. degree in Computer Eng. Dep. of Sharif Univ. of Tech. in three years and who's GPA has been the most GPA in this department up to the graduation date.
Scholarship from Canadian International Graduate Student, 2000.
Scholarship from Communications and Information Technology Ontario, 2000.
Second rank in the ACM regional contest, Tehran, Iran, 1999.
Fourth rank in the ACM regional contest , Khanpur, India, 1999.
Silver Medal in the 9th International Olympiad in Informatics (IOI'97), South Africa, 1997.
Gold Medal in 6th Iranian Informatics Olympiad, 1996.
Erdos number 3!

Research Interests :

Data Structures and Combinatorial Algorithms
Algorithmic Graph Theory
Embeddings and its Algorithmic Aspects
Distributed and Mobile Computing
Computational Complexity
Game Theory and Combinatorial Auctions
Combinatorial Optimization
Random Structures and Algorithms
Real-time Machine Vision and Image Processing.

Research Experience:

Short-time Research in Microsoft Research (Silicon Valley), September 2004, Research on Auction Design.
Research Intern, Microsoft Research (Redmond), Theory group, Summer 2004, January 2004, and September 2003, Research under mentorship of Kamal Jain. Worked on problems related to connectivity and cut, more especially feedback vertex set and generalized deadlock resolution, ATSP, Bidirected LP. See the conference paper No. 20 above. Also I worked on analyzing random walk for random SAT, random 3-SAT, probabilistic oblivious routing.
Short-time Research in Workshop on Triangulations of Point Sets: Applications, Structures, Algorithms, Mathematical Sciences Research Institute (MSRI), July 2003.
Research Intern, IBM T. J. Watson Research center, Theory of Computation group, Summer 2002, Research under mentorship of Gregory Sorkin. Worked on problems related to random satisfiability and random graphs. See the journal paper No. 11 and Research report paper No. 3 above.
Short-time Research in Workshop on Perfect Graphs, American Institute of Mathematics (AIM), October-November 2002. The workshop was organized by Paul Seymour and Robin Thomas.
Research Assistant in Massachusetts Institute of Technology, Fall 2002, Spring 2003, Spring 2004, Worked with Professor Erik D. Demaine and Professor Tom Leighton. See my publications above.
Research Assistant in University of Waterloo, Fall 2000, Spring and Summer 2001. Worked with Professor Naomi Nishimura on problems related to Interval Routing, Subgraph Isomorphism and Algorithms on Graphs of (Locally) Bounded Treewidth. See my publications above.
Participating in Problem Solving Sessions in University of Waterloo, 2000-2001 (see http://daisy.uwaterloo.ca/~eddemain/ProblemSession for more information).
Member of Sharif CE Middle Size RoboCup project 1999-2000, which got many International achievements during the last 2 years, Section of Algorithms (see http://sharif.ac.ir/~ceinfo/robocup for more information about this project).
Research Assistant in Sharif University of Technology, 1999-2000. Worked on problems related to Parallel Computing. See the journal paper No. 4 above.
Research in IPM Research Center in Iran, 1997-1999. Worked on problems related to Advanced Graph Theory, more especially on Uniquely List Colorable Graphs and Factors in Hypergraphs. See the journal paper No. 1 above.
Scientific Committe of Iranian National Computer Olympiad, 1997-2000. Worked on designing problems and organizing national competitions and training camps.
Editor-in-chief of Olympiad Quarterly magazine, 1998-2000.

Teaching Experience:

Teaching Assistant of these courses:

Numerical Methods of Applied Mathematics, MIT, Fall 2003.
Numerical Analysis, MIT, Spring 2002.
Combinatorial Optimization, MIT, Fall 2001.
Data Structures and Data Management, University of Waterloo, Winter and Spring 2001.
Foundations of Sequential Programs, University of Waterloo, Fall 2000.
Data structures and Algorithms, Sharif University of Tech., Spring 1999 & Spring 2000.
Foundations of Computer Science II , Fall 1999.

Teaching for Iranian Informatics Olympiad Teams, 1998-2000.

Software Skills :

Programming in Basic, Pascal, PC 8086 Assembly, C, C++, LISP, Prolog, Smalltalk, Maple, Lex/Flex, YACC/Bison, Fortran, TeX and LaTeX, PostScript, Standard ML, HTML 4, Java, Matlab, JavaScript, Mathematica, DirectX 7.
Experienced in working on Unix, Linux and Windows Operating systems.

Curent References:

At MIT:

Professor Erik Demaine,
Lab. for Computer Science
Massachusetts Institute of Technology
Cambridge, MA, U.S.A.
Tel: (617) 253-6871
Email: edemaine@MIT.EDU

Professor Tom Leighton,
Department of Mathematics and Lab. for Computer Science
Massachusetts Institute of Technology
Cambridge, MA, U.S.A.
Tel: (617) 253-3037
Email: ftl@theory.lcs.MIT.EDU

Professor Nancy Lynch,
Lab. for Computer Science
Massachusetts Institute of Technology
Cambridge, MA, U.S.A.
Tel: (617) 253-7225
Email: lynch@theory.lcs.MIT.EDU

At University of Waterloo:

Professor Naomi Nishimura,
Department of Computer Science
University of Waterloo
Waterloo, Ontario, Canada
Tel: (519) 888-4567 x4835
Email: nishi@uwaterloo.ca

Professor Jim Geelen,
Department of Combinatorics and Optimization
University of Waterloo
Waterloo, Ontario, Canada
Tel: (519) 888-4567 x5594
Email: jfgeelen@math.uwaterloo.ca