Email:

tomas@theory.stanford.edu

High School:

Lycée Franco-Argentin ''Jean Mermoz,'' Buenos Aires, Argentina.

Undergraduate School:

Stanford University, Stanford, CA 94305.

Graduate School:

Stanford University, Stanford, CA 94305.

Degrees Conferred:

- French and Argentine Baccalaureate, with Distinction, Buenos Aires, Argentina, November 1982.
- B.S., Mathematical and Computational Science, Stanford University, with Distinction and Departmental Honors, June 1986.
- Ph.D., Computer Science, Stanford University, June 1990. High Pass in Departmental Comprehensive Exams and in Analysis of Algorithms Qualifying Exam, 1987. Advisor: Donald E. Knuth.

Honors:

- President's Award for Academic Excellence in the Freshman Year, Stanford University, 1984.
- Phi Beta Kappa, 1985.
- IBM Fellowship, 1986.
- AT&T Bell Fellowship, 1987.
- Best Student Paper Award in 21st Annual ACM Symposium on Theory of Computing, 1989.
- Invited Speaker to Combinatorics 2006, Pavol Hell's 60th Birthday Celebration, Victoria, BC, Canada.
- Invited Speaker to Mathematics CSP 2006, Oxford.
- Invited Speaker to Discrete Mathematics 2006, Victoria, BC, Canada.
- Invited Speaker to Algebraic Graph Theory 2009, Gert Sabidussi's 80th Birthday Celebration, Dubrovnik, Croatia.

Interest Areas:

Design and Analysis of Algorithms, Computational Complexity Theory,
Parallel Computation, Graph Theory, Discrete Mathematics, Online
Algorithms, Approximation Algorithms.

Work Experience:

- 1996-2004: Research with Prof. Rajeev Motwani at Stanford University.
- 1992-1995: Research at IBM Almaden Research Center, San Jose, CA.
- 1991: Research at Bell Communications Research, Morristown, NJ.
- 1987-1990: Research at IBM Almaden Research Center, San Jose, CA.
- Summer 1988: Research at AT&T Bell Laboratories, Murray Hill, NJ.
- Summer 1987: Research at Xerox PARC, Palo Alto, CA.
- Summers 1985-1986: Research with Prof. Zohar Manna at Stanford University.
- Summer 1984: Programming with Computer Science Dept., Stanford University.

Research Papers:

- Toetjes. Amer. Math. Monthly (1990) 785-794.
- Optimal algorithms for approximate clustering. (with D. Greene) Proc. 20th Ann. ACM Symp. on Theory of Computing (1988) 434-444.
- Reliable computation by networks in the presence of noise. IEEE Trans. on Information Theory 35-3 (1989) 569-571.
- Multiparty communication complexity. (with D. Dolev) FOCS (1989) 428-433.
- Determinism vs. nondeterminism in multiparty communication complexity. (with D. Dolev) SIAM J. Comput. 21 (1992) 889-895.
- A new fixed point approach for stable networks and stable marriages. J. Computer and System Sciences 45 (1992) 233-284.
- A new fixed point approach for stable networks and stable marriages. Proc. 21st Ann. ACM Symp. on Theory of Computing (1989) 513-522.
- Representations in product graphs. J. Graph Theory. 16 (1992) 467-488.
- Network flow and 2-satisfiability. Algorithmica 11-3 (1994) 291-319.
- Stable Networks and Product Graphs. Doctoral dissertation, Stanford University (1991).
- Stable Networks and Product Graphs. Memoirs Amer. Math. Society Vol. 116 No. 555 (1995) 223 pp.
- Clique partitions, graph compression, and speeding-up algorithms. (with R. Motwani) J. Computer and System Sciences 51-2 (1995) 261-272.
- Clique partitions, graph compression, and speeding-up algorithms. (with R. Motwani) Proc. 23rd Ann. ACM Symp. on Theory of Computing (1991) 123-133.
- Amortized communication complexity. (with E. Kushilevitz, M. Naor, N. Nisan) Proc. 32nd Ann. IEEE Symp. on Found. of Computer Science (1991) 239-248.
- Amortized communication complexity. (with E. Kushilevitz, M. Naor, N. Nisan) SIAM J. Comput. 24-4 (1995) 736-750.
- A quadratic form for points in space, IBM Internal Note, 1993.
- Finding a vertex in a polytope, Bell Labs (with P. Vaidya).
- Decidability and undecidability of equivalence for linear datalog with applications to normal-form optimizations (with Y. Saraiya) International Conference on Database Theory (1992) 297-311.
- The benefits of relaxing punctuality. (with R. Alur, T. Henzinger) Proc. 10th ACM Symp. on Principles of Distributed Computing (1991) 139-152.
- The benefits of relaxing punctuality. (with R. Alur, T. Henzinger) J. ACM 43 (1996) 116-146.
- Circuit switched link simulation: algorithms, complexity and implementation. (with A. Greenberg, V. Ramachandran, M. Rauch, L. Wang) (1992).
- Balanced Matroids. (with M. Mihail) Proc. 24th Ann. ACM Symp. on Theory of Computing (1992) 26-38.
- Monotone monadic SNP and constraint satisfaction. (with M. Vardi) Proc. 25th Ann. ACM Symp. on Theory of Computing (1993) 612-622.
- The computational structure of monotone monadic SNP and constraint satisfaction: a study through Datalog and group theory. (with M. Vardi) SIAM J. Comput. 28 (1998) 57-104.
- A sublinear parallel algorithm for stable matching. (with N. Megiddo, S. Plotkin) Theoretical Computer Science 233 (2000) 297-308.
- A sublinear parallel algorithm for stable matching. (with N. Megiddo, S. Plotkin) Proc. 5th Ann. ACM-SIAM Symp. on Discrete Algorithms (1994) 632-637.
- Homomorphism closed vs. existential positive. (with M. Vardi) Logic in Comp. Sci. (2003), 311-320.
- Classification of homomorphisms to oriented cycles and k-partite satisfiability. SIAM J. Discrete Math 14 (2001) 471-480.
- List homomorphisms to reflexive graphs. (with P. Hell) J. Comb. Theory Series B 72-2 (1998) 236-250.
- List homomorphisms and circular arc graphs. (with P. Hell, J. Huang) Combinatorica 19-4 (1999) 487-505.
- Bi-arc graphs and the complexity of list homomorphisms (with P. Hell, J. Huang) J. Graph Theory 42 (1999) 61-80.
- The structure of bi-arc trees (with P. Hell, J. Huang) Discrete Math. 307 (2007) 393-401.
- List homomorphisms and retractions to reflexive digraphs. (with P. Hell, J. Huang)
- Complexity of graph partitions problems (with P. Hell, S. Klein, R. Motwani) Proc. 31st Ann. ACM Symp. on Theory of Computing (1999) 464-472.
- List partitions. (with P. Hell, S. Klein, R. Motwani) SIAM J. Discrete Mathematics 16 (2003) 449-478.
- Full constraint satisfaction problems. (with P. Hell) SIAM J. Computing. 36 (2006) 230-246.
- Near-unanimity functions and varieties of reflexive graphs. (with R. Brewster, P. Hell, J. Huang and G. MacGillivray) SIAM J. on Discrete Math. 22 (2008) 938--960.
- Width one, bounded strict width, and chordal extensible graphs. (with P. Hell)
- List homomorphisms of graphs with bounded degrees. (with P. Hell, J. Huang) Discrete Math. 307 (2007) 386-392.
- Brooks type theorems for pair-list colourings and list homomorphisms. (with P. Hell, J. Huang) SIAM J. Discr. Math 22-1.
- Extension problems with degree bounds. (with P. Hell, J. Huang)
- Acyclic homomorphisms and circular colorings of digraphs. (with P. Hell, B. Mohar) SIAM J. Discrete Math 17 (2003) 161-169.
- Digraph matrix partitions and trigraph homomorphisms. (with P. Hell, K. Tucker-Nally) Discrete Applied Math. 154 (2006) 2458-2469.
- List matrix partitions of chordal graphs. (with P. Hell, S. Klein, L.T. Nogueira, F. Protti). Latin Amer. Theor. Inform. (LATIN 2004) 100-108.
- List matrix partitions of chordal graphs. (with P. Hell, S. Klein, L.T. Nogueira, F. Protti). Theoretical Computer Science 349-1 (2005) 52-66.
- Matrix partitions of perfect graphs. (with P. Hell), Claude Berge Memorial Volume, Discrete Math. 306 (2006) 2450-2460.
- On realizations of point determining graphs, and obstructions to full homomorphisms. (with P. Hell) Discrete Mathematics 308 (2008), 1639-1652
- Two algorithms for general list matrix partitions. (with P. Hell, D. Kral, J. Sgall) SODA 2005, 870-876.
- Partition into k-vertex subgraphs of k-partite graphs. (with C. Subi) Electronic Colloquium on Computational Complexity (ECCC) TR06-016, 2006.
- Fanout limitations on constraint systems. Theoretical Computer Science 255 (2001) 281-293.
- Online channel allocation in FDMA networks with reuse constraints. (with S. Shende) 2nd International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications (1998).
- Online channel allocation in FDMA networks with reuse constraints. (with S. Shende) Information Processing Letters 67 (1998) 295-302.
- Incremental clustering and dynamic information retrieval. (with M. Charikar, C. Chekuri, R. Motwani) Proc. 29th Ann. ACM Symp. on Theory of Computing (1997) 626-635.
- Incremental clustering and dynamic information retrieval. (with M. Charikar, C. Chekuri, R. Motwani) SIAM J. Comput 33-6 (2004) 1417-1440.
- Computing the median with uncertainty. (with R. Motwani, R. Panigrahy, C. Olston, J. Widom) Proc. 32nd Ann. ACM Symp. on Theory of Computing (2000) 602-607.
- Computing the median with uncertainty. (with R. Motwani, R. Panigrahy, C. Olston, J. Widom) SIAM J. Computing 32 (2003) 538-547.
- Finding long paths and cycles in sparse Hamiltonian graphs. (with R. Motwani, C. Subi) Proc. 32nd Ann. ACM Symp. on Theory of Computing (2000) 524-529.
- Approximating the longest cycle problem in sparse graphs. (with R. Motwani, C. Subi) SIAM J. Computing. 31 (2002) 1596-1607.
- Web caching with request reordering. (with R. Motwani, R. Panigrahy, A. Zhu) Proc. 13th Ann. ACM-SIAM Symp. on Discrete Algorithms (2002) 104-105.
- Combining request scheduling with web caching. (with R. Motwani, R. Panigrahy, S. Seiden, R. van Stee, A. Zhu) Theor. Comput. Sci 324 (2004) 201-218.
- A combinatorial algorithm for MAX CSP. (with M. Datar, A. Gionis, R. Motwani, R. Panigrahy) Information Processing Letters 85 (2003) 307-315.
- Worst-case time bounds for coloring and satisfiability problems. (with R. Motwani) J. Algorithms 45 (2002) 192-201.
- Computing shortest paths with uncertainty. (with R. Motwani, L. O'Callaghan, C. Olston, R. Panigrahy) STACS 2003, 367-378.
- Computing shortest paths with uncertainty. (with R. Motwani, L. O'Callaghan, C. Olston, R. Panigrahy) J. Algorithms 62 (2007) 1-18.
- Representing graph metrics with fewest edges. (with A. Meyerson, R. Motwani, L. O'Callaghan, R. Panigrahy) STACS 2003, 355-366.
- Constraint satisfaction on finite groups with near subgroups, Electronic Colloquium on Computational Complexity (ECCC) TR05-005, 2005.
- Strong near subgroups and left gyrogroups. J. Algebra 259 (2003).
- Dichotomies for classes of homomorphism problems involving unary functions. (with F. Madelaine, I.A. Stewart) Theoretical Computer Science 314 (2004), 1-43.
- On Barnette's conjecture (weaker version). (with C. Subi)
- On Barnette's conjecture. (with C. Subi) Electronic Colloquium on Computational Complexity (ECCC) TR06-015, 2006.
- Disks on a tree: analysis of a combinatorial game. (with C. Subi) SIAM J. Discrete Math, 19-3 (2006), 543-552.
- Online distributed predicate evaluation. (with R. Motwani, L. O'Callaghan, R. Panigrahy, D. Thomas) Technical Report, Stanford University, 2003. http://dbpubs.stanford.edu/pub/2003-81.
- Querying priced information in databases: the conjunctive case. (with R. Carmo, Y. Kohayakawa, E.S. Laber, R. Motwani, L. O'Callaghan, R. Panigrahy, D. Thomas) ACM Transactions on Algorithms 3-1 (2007).
- Algorithms for multi-product pricing. ICALP 2004, 72-83 (with G. Aggarwal, R. Motwani, A. Zhu)
- A dichotomy theorem on fixed points of several nonexpansive mappings. SIAM J. Discrete Math 20-2 (2006) 291-301.
- Classification of bipartite boolean constraint satisfaction through delta-matroid intersection. (with D. Ford) Electronic Colloquium on Computational Complexity (ECCC) TR05-016, 2005.
- Classification of bipartite boolean constraint satisfaction through delta-matroid intersection. (with D. Ford) SIAM J. Discrete Math. 20-2 (2006) 372--394.
- Closures and dichotomies for quantified constraints. (with P. Kolaitis) Electronic Colloquium on Computational Complexity (ECCC) TR06-160, 2006.
- Algorithms for the database layout problem. (with G. Aggarwal, R. Motwani, R. Panigrahy, A. Zhu) ICDT 2005, 189-203.
- Anonimyzing tables. (with G. Aggarwal, K. Kenthapadi, R. Motwani, R. Panigrahy, D. Thomas, A. Zhu) ICDT 2005, 246-258.
- Approximation algorithms for k-anonymity. (with G. Aggarwal, K. Kenthapadi, R. Motwani, R. Panigrahy, D. Thomas, A. Zhu) JOPT (J. Privacy Technology) 2005.
- Finding large cycles in Hamiltonian graphs. (with R. Motwani) Symp. on Discr. Alg. (2005) 166-175.
- Finding large cycles in Hamiltonian graphs. (with R. Motwani) Electronic Colloquium on Computational Complexity (ECCC) TR06-156, 2006.
- Finding large cycles in Hamiltonian graphs. (with R. Motwani) Discrete Applied Math. 158 (2010) 882-893.
- Channel assignment in wireless networks and classification of minimum graph homomorphism. (with G. Aggarwal, R. Motwani, A. Zhu) Electronic Colloquium on Computational Complexity (ECCC) TR06-040, 2006.
- Achieving anonymity via clustering. (with G. Aggarwal, K. Kenthapadi, S. Khuller, R. Panigrahy, D. Thomas, A. Zhu) PODS 2006, 153-162.
- $k$-connected spanning subgraphs of low degree. (with R. Motwani, A. Zhu) Electronic Colloquium on Computational Complexity (ECCC) TR06-041, 2006.
- Generalized colourings (matrix partitions) of cographs. (with P. Hell, W. Hochstaettler)
- A local switch Markov chain on given degree graphs with application in connectivity of Peer-to-Peer networks. (with A. Guetz, M. Mihail, A. Saberi) FOCS 2006, 69-76.
- List matrix partitions of interval graphs and its generalizations. (with P. Hell)
- Constraint satisfaction: a personal perspective (ps file) , (pdf file). Electronic Colloquium on Computational Complexity (ECCC) TR06-021, 2006.
- A practical computer program that diagnoses diseases in actual patients. (with C. Feder), Infinity publishing company, 117 pp.
- Patent US 7,624,030: Computer-implemented medical analytics method and system employing a modified mini-max procedure. This patent covers a practical computer program that diagnoses diseases in actual patients. (with C. Feder)
- Mini-Max procedure versus Bayes formula to calculate probability of a medical diagnosis. (with C. Feder)
- Best cost-benefit clinical data next to investigate at each diagnostic step. (with C. Feder)
- Artifice for databases that do not include all known diseases and clinical data. (with C. Feder)
- Complex clinical presentations and their models and clinical data. (with C. Feder)
- Simultaneous recommendation of best cost-benefit clinical data. (with C. Feder)
- Online algorithms for edge coloring. (with R. Motwani and R. Panigrahy)
- Matrix partitions with finitely many obstructions. (with P. Hell and W. Xie)
- Multi-domain bipartite Boolean constraint satisfaction and delta-matroids.
- Approximating Nash equilibria using small-support strategies. (with H. Nazerzadeh and A. Saberi) ACM Conference on Electronic Commerce (2007) 352-354.
- On quadrangles and convex figures in the plane.
- Edge list homomorphisms. (with P. Hell)
- Partitioning columns for secure distributed databases. (with V. Ganapathy, H. Garcia-Molina, R. Motwani, D. Thomas)
- Distributing data for secure database services. (with V. Ganapathy, H. Garcia-Molina, R. Motwani, D. Thomas) ICDT / EDBT 2011
- Distributing data for secure database services. (with V. Ganapathy, H. Garcia-Molina, R. Motwani, D. Thomas) Transactions on Data Privacy 5 (2012) 253-272
- Virus propagation in a graph. (with A. Saberi)
- Approximate pure equilibria in cut games. (with A. Asadpour and A. Saberi)
- Spanning trees and cuts. (with A. Asadpour and A. Saberi)
- On the graph turnpike problem. (with R. Motwani) Inform. Proc. Letters 109 (2009).
- Nearly tight bounds on the number of Hamiltonian cycles of the hypercube and generalizations. (with C. Subi) Electronic Colloquium on Computational Complexity (ECCC) TR07-063, 2007.
- Nearly tight bounds on the number of Hamiltonian cycles of the hypercube and generalizations. (with C. Subi) Information Processing Letters 109 (2009), 267-272.
- Matchings and cycle decompositions in hypercubes. (with C. Subi)
- Is edge 3-colorability reconstructible? (with R. Motwani)
- List homomorphisms to balanced digraphs. (with P. Hell and A. Rafiey)
- Anonymizing graphs. (with S.U. Nabar and E. Terzi)
- Dichotomy for three-structured trigraph list homomorphism problems. (with P. Hell, D.G. Schell, and J. Stacho)
- Approximating the minimum chain completion problem. (with H. Mannila and E. Terzi)
- Graceful almost symmetrical trees. (with C. Subi)
- Graceful isometric embeddings of trees on n-cubes. (with C. Subi)
- Graceful labelings of paths on grids. (with C. Subi)
- On the complexity of MM1SNP. (with M. Bodirky and H. Chen)
- On the complexity of MMSNP. (with M. Bodirky and H. Chen) SIDMA 26 (2012) 404-414.
- An approximation algorithm for a scheduling problem. (with R. Motwani)
- Retractions to pseudoforests. (with P. Hell, P. Jonsson, A. Krokhin, and G. Nordh) SIAM J. on Discrete Math (SIDMA), 24-1 (2010).
- Interval graphs, adjusted interval digraphs,and reflexive list homomorphisms. (with P. Hell, J. Huang, and A. Rafiey) Discr. Appl. Math. 160 (2012) 697-707.
- Maximum gap labelings of graphs. (with C. Subi) Inform. Proc. Let., to appear.
- Minimum uniform gap labelings of trees. (with C. Subi)
- Hitting set, spanning trees, and the minimum length corridor problem. (with C. Subi)
- Embedding trees in Cartesian products by an edge. (with C. Subi)
- Homomorphic image d-cubes of d+1-cubes are retracts. (with C. Subi)
- On hypercube labellings and antipodal monochromatic paths. Discr. Appl. Math., to appear (with C. Subi)
- On monochromatic path and rainbow triangles in tournaments. (with C. Subi)
- Orthogonal matching decompositions of matching and Hamilton decompositions. (with C. Subi)
- Line graphs of cliques and clique minors. (with C. Subi)
- Packing edge-disjoint triangles into given graphs. Electronic Colloquium on Computational Complexity (ECCC) TR12-013, 2012. (with C. Subi)
- On 2 to the r, and (2 to the r)-1, dividing (3 to the s)-1. (with C. Subi)
- Irreducible polynomials for primes. (with C. Subi)
- Connected point determining obstructions. (with P. Hell)
- Obstructions to partitions of chordal graphs. (with P. Hell and S.N. Rizi) Discrete Mathematics, to appear.
- Random dominating sets and Markov chains. (with P. Diaconis and A. Saberi)
- On graphs with many minimum cuts. (with S.O. Ghara and A. Saberi)
- On thinness of spanning trees in series-parallel and planar graphs. (with A. Saberi)
- Matrix partitions of split graphs. (with P. Hell and O. Shklarsky)
- Graphs admitting k-NU operations. Part 1: The reflexive case. (with P. Hell, B. Larose, C. Loten, M. Siggers, and C. Tardif) SIAM J. Discr. Math 27-4 (2014).
- Graphs admitting k-NU operations. Part 2: The irreflexive case. (with P. Hell, B. Larose, C. Loten, M. Siggers, and C. Tardif)
- Greedy versus optimum for the $k$-median problem. (with S. Ehsani and A. Saberi)
- On a conjecture of Erdos, Faber, and Lovasz. (with C. Subi)
- Partitioning graphs into l-walks. (with C. Subi)
- Edge-coloring almost bipartite multigraphs. (with C. Subi) Inform. Proc. Letters, to appear.
- At most cubic caterpillars are not reconstructible from subtree data. (with C. Subi)
- On a conjecture on iterated line graphs. (with C. Subi)
- Matrix partitions of transitive digraphs. (with P. Hell and C. Hernandez Cruz)
- Matrix partitions of bipartite graphs. (with P. Hell and P. Valadkhan)
- Optimizing list homomorphisms of reflexive graphs. (with P. Hell and P. Valadkhan)