Welcome to Tomás Feder's Homepage!

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:

  1. French and Argentine Baccalaureate, with Distinction, Buenos Aires, Argentina, November 1982.
  2. B.S., Mathematical and Computational Science, Stanford University, with Distinction and Departmental Honors, June 1986.
  3. 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:

  1. President's Award for Academic Excellence in the Freshman Year, Stanford University, 1984.
  2. Phi Beta Kappa, 1985.
  3. IBM Fellowship, 1986.
  4. AT&T Bell Fellowship, 1987.
  5. Best Student Paper Award in 21st Annual ACM Symposium on Theory of Computing, 1989.
  6. Invited Speaker to Combinatorics 2006, Pavol Hell's 60th Birthday Celebration, Victoria, BC, Canada.
  7. Invited Speaker to Mathematics CSP 2006, Oxford.
  8. Invited Speaker to Discrete Mathematics 2006, Victoria, BC, Canada.

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

Work Experience:

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

  • Logic, mathematics, and computational complexity.

  • Linked structures philosophical summary.

  • A problem on rectangles and convex figures.

  • A problem on trees and cubes.

  • Constraint satisfaction: a personal perspective (ps file) , (pdf file).

  • SOCCER MILLENIUM game I invented (gcc code gdm.c) , (compiled gdm.out).

    • Research Papers:

    1. Toetjes. Amer. Math. Monthly (1990) 785-794.
    2. Optimal algorithms for approximate clustering. (with D. Greene) Proc. 20th Ann. ACM Symp. on Theory of Computing (1988) 434-444.
    3. Reliable computation by networks in the presence of noise. IEEE Trans. on Information Theory 35-3 (1989) 569-571.
    4. Multiparty communication complexity. (with D. Dolev) FOCS (1989) 428-433.
    5. Determinism vs. nondeterminism in multiparty communication complexity. (with D. Dolev) SIAM J. Comput. 21 (1992) 889-895.
    6. A new fixed point approach for stable networks and stable marriages. J. Computer and System Sciences 45 (1992) 233-284.
    7. A new fixed point approach for stable networks and stable marriages. Proc. 21st Ann. ACM Symp. on Theory of Computing (1989) 513-522.
    8. Representations in product graphs. J. Graph Theory. 16 (1992) 467-488.
    9. Network flow and 2-satisfiability. Algorithmica 11-3 (1994) 291-319.


    10. Stable Networks and Product Graphs. Doctoral dissertation, Stanford University (1991).
    11. Stable Networks and Product Graphs. Memoirs Amer. Math. Society Vol. 116 No. 555 (1995) 223 pp.


    12. Clique partitions, graph compression, and speeding-up algorithms. (with R. Motwani) J. Computer and System Sciences 51-2 (1995) 261-272.
    13. Clique partitions, graph compression, and speeding-up algorithms. (with R. Motwani) Proc. 23rd Ann. ACM Symp. on Theory of Computing (1991) 123-133.
    14. Amortized communication complexity. (with E. Kushilevitz, M. Naor, N. Nisan) Proc. 32nd Ann. IEEE Symp. on Found. of Computer Science (1991) 239-248.
    15. Amortized communication complexity. (with E. Kushilevitz, M. Naor, N. Nisan) SIAM J. Comput. 24-4 (1995) 736-750.
    16. 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.
    17. The benefits of relaxing punctuality. (with R. Alur, T. Henzinger) Proc. 10th ACM Symp. on Principles of Distributed Computing (1991) 139-152.
    18. The benefits of relaxing punctuality. (with R. Alur, T. Henzinger) J. ACM 43 (1996) 116-146.
    19. Circuit switched link simulation: algorithms, complexity and implementation. (with A. Greenberg, V. Ramachandran, M. Rauch, L. Wang) (1992).
    20. Balanced Matroids. (with M. Mihail) Proc. 24th Ann. ACM Symp. on Theory of Computing (1992) 26-38.
    21. Monotone monadic SNP and constraint satisfaction. (with M. Vardi) Proc. 25th Ann. ACM Symp. on Theory of Computing (1993) 612-622.
    22. 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.
    23. A sublinear parallel algorithm for stable matching. (with N. Megiddo, S. Plotkin) Theoretical Computer Science 233 (2000) 297-308.
    24. A sublinear parallel algorithm for stable matching. (with N. Megiddo, S. Plotkin) Proc. 5th Ann. ACM-SIAM Symp. on Discrete Algorithms (1994) 632-637.
    25. Homomorphism closed vs. existential positive. (with M. Vardi) Logic in Comp. Sci. (2003), 311-320.
    26. Classification of homomorphisms to oriented cycles and k-partite satisfiability. SIAM J. Discrete Math 14 (2001) 471-480.
    27. List homomorphisms to reflexive graphs. (with P. Hell) J. Comb. Theory Series B 72-2 (1998) 236-250.
    28. List homomorphisms and circular arc graphs. (with P. Hell, J. Huang) Combinatorica 19-4 (1999) 487-505.
    29. Bi-arc graphs and the complexity of list homomorphisms (with P. Hell, J. Huang) J. Graph Theory 42 (1999) 61-80.
    30. The structure of bi-arc trees (with P. Hell, J. Huang) Discrete Math. 307 (2007) 393-401.
    31. List homomorphisms and retractions to reflexive digraphs. (with P. Hell, J. Huang)
    32. Complexity of graph partitions problems (with P. Hell, S. Klein, R. Motwani) Proc. 31st Ann. ACM Symp. on Theory of Computing (1999) 464-472.
    33. List partitions. (with P. Hell, S. Klein, R. Motwani) SIAM J. Discrete Mathematics 16 (2003) 449-478.
    34. Full constraint satisfaction problems. (with P. Hell) SIAM J. Computing. 36 (2006) 230-246.
    35. Near-unanimity functions and varieties of graphs. (with R. Brewster, P. Hell, J. Huang and G. MacGillivray) submitted.
    36. Width one, bounded strict width, and chordal extensible graphs. (with P. Hell)
    37. List homomorphisms of graphs with bounded degrees. (with P. Hell, J. Huang) Discrete Math. 307 (2007) 386-392.
    38. Brooks type theorems for pair-list colourings and list homomorphisms. (with P. Hell, J. Huang)
    39. Extension problems with degree bounds. (with P. Hell, J. Huang)
    40. Acyclic homomorphisms and circular colorings of digraphs. (with P. Hell, B. Mohar) SIAM J. Discrete Math 17 (2003) 161-169.
    41. Digraph matrix partitions and trigraph homomorphisms. (with P. Hell, K. Tucker-Nally) Discrete Applied Math. 154 (2006) 2458-2469.
    42. List matrix partitions of chordal graphs. (with P. Hell, S. Klein, L.T. Nogueira, F. Protti). Latin Amer. Theor. Inform. (LATIN 2004) 100-108.
    43. List matrix partitions of chordal graphs. (with P. Hell, S. Klein, L.T. Nogueira, F. Protti). Theoretical Computer Science 349-1 (2005) 52-66.
    44. Matrix partitions of perfect graphs. (with P. Hell), Claude Berge Memorial Volume, Discrete Math. 306 (2006) 2450-2460.
    45. On realizations of point determining graphs, and obstructions to full homomorphisms. (with P. Hell) Discrete Mathematics 308 (2008), 1639-1652
    46. Two algorithms for general list matrix partitions. (with P. Hell, D. Kral, J. Sgall) SODA 2005, 870-876.
    47. Partition into k-vertex subgraphs of k-partite graphs. (with C. Subi) Electronic Colloquium on Computational Complexity (ECCC) TR06-016, 2006.
    48. Fanout limitations on constraint systems. Theoretical Computer Science 255 (2001) 281-293.
    49. 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).
    50. Online channel allocation in FDMA networks with reuse constraints. (with S. Shende) Information Processing Letters 67 (1998) 295-302.
    51. 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.
    52. Incremental clustering and dynamic information retrieval. (with M. Charikar, C. Chekuri, R. Motwani) SIAM J. Comput 33-6 (2004) 1417-1440.
    53. 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.
    54. Computing the median with uncertainty. (with R. Motwani, R. Panigrahy, C. Olston, J. Widom) SIAM J. Computing 32 (2003) 538-547.
    55. 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.
    56. Approximating the longest cycle problem in sparse graphs. (with R. Motwani, C. Subi) SIAM J. Computing. 31 (2002) 1596-1607.
    57. Web caching with request reordering. (with R. Motwani, R. Panigrahy, A. Zhu) Proc. 13th Ann. ACM-SIAM Symp. on Discrete Algorithms (2002) 104-105.
    58. 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.
    59. A combinatorial algorithm for MAX CSP. (with M. Datar, A. Gionis, R. Motwani, R. Panigrahy) Information Processing Letters 85 (2003) 307-315.
    60. Worst-case time bounds for coloring and satisfiability problems. (with R. Motwani) J. Algorithms 45 (2002) 192-201.
    61. Computing shortest paths with uncertainty. (with R. Motwani, L. O'Callaghan, C. Olston, R. Panigrahy) STACS 2003, 367-378.
    62. Computing shortest paths with uncertainty. (with R. Motwani, L. O'Callaghan, C. Olston, R. Panigrahy) J. Algorithms 62 (2007) 1-18.
    63. Representing graph metrics with fewest edges. (with A. Meyerson, R. Motwani, L. O'Callaghan, R. Panigrahy) STACS 2003, 355-366.
    64. Constraint satisfaction on finite groups with near subgroups, Electronic Colloquium on Computational Complexity (ECCC) TR05-005, 2005.
    65. Strong near subgroups and left gyrogroups. J. Algebra 259 (2003).
    66. Dichotomies for classes of homomorphism problems involving unary functions. (with F. Madelaine, I.A. Stewart) Theoretical Computer Science 314 (2004), 1-43.
    67. On Barnette's conjecture (weaker version). (with C. Subi)
    68. On Barnette's conjecture. (with C. Subi) Electronic Colloquium on Computational Complexity (ECCC) TR06-015, 2006.
    69. Disks on a tree: analysis of a combinatorial game. (with C. Subi) SIAM J. Discrete Math, 19-3 (2006), 543-552.
    70. 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.
    71. 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).
    72. Algorithms for multi-product pricing. ICALP 2004, 72-83 (with G. Aggarwal, R. Motwani, A. Zhu)
    73. A dichotomy theorem on fixed points of several nonexpansive mappings. SIAM J. Discrete Math 20-2 (2006) 291-301.
    74. Classification of bipartite boolean constraint satisfaction through delta-matroid intersection. (with D. Ford) Electronic Colloquium on Computational Complexity (ECCC) TR05-016, 2005.
    75. Classification of bipartite boolean constraint satisfaction through delta-matroid intersection. (with D. Ford) SIAM J. Discrete Math. 20-2 (2006) 372--394.
    76. Closures and dichotomies for quantified constraints. (with P. Kolaitis) Electronic Colloquium on Computational Complexity (ECCC) TR06-160, 2006.
    77. Algorithms for the database layout problem. (with G. Aggarwal, R. Motwani, R. Panigrahy, A. Zhu) ICDT 2005, 189-203.
    78. Anonimyzing tables. (with G. Aggarwal, K. Kenthapadi, R. Motwani, R. Panigrahy, D. Thomas, A. Zhu) ICDT 2005, 246-258.
    79. Approximation algorithms for k-anonymity. (with G. Aggarwal, K. Kenthapadi, R. Motwani, R. Panigrahy, D. Thomas, A. Zhu) JOPT (J. Privacy Technology).
    80. Finding large cycles in Hamiltonian graphs. (with R. Motwani) Symp. on Discr. Alg. (2005) 166-175.
    81. Finding large cycles in Hamiltonian graphs. (with R. Motwani) Electronic Colloquium on Computational Complexity (ECCC) TR06-156, 2006.
    82. 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.
    83. Achieving anonymity via clustering. (with G. Aggarwal, K. Kenthapadi, S. Khuller, R. Panigrahy, D. Thomas, A. Zhu) PODS 2006, 153-162.
    84. $k$-connected spanning subgraphs of low degree. (with R. Motwani, A. Zhu) Electronic Colloquium on Computational Complexity (ECCC) TR06-041, 2006.
    85. Generalized colourings (matrix partitions) of cographs. (with P. Hell, W. Hochstaettler)
    86. 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.
    87. List matrix partitions of interval graphs and its generalizations. (with P. Hell)
    88. Constraint satisfaction: a personal perspective (ps file) , (pdf file). Electronic Colloquium on Computational Complexity (ECCC) TR06-021, 2006.
    89. Mini-Max procedure versus Bayes formula to calculate probability of a medical diagnosis. (with C. Feder)
    90. Online algorithms for edge coloring. (with R. Motwani and R. Panigrahy)
    91. Matrix partitions with finitely many obstructions. (with P. Hell and W. Xie)
    92. Multi-domain bipartite Boolean constraint satisfaction and delta-matroids.
    93. Approximating Nash equilibria using small-support strategies. (with H. Nazerzadeh and A. Saberi) ACM Conference on Electronic Commerce (2007) 352-354.
    94. On quadrangles and convex figures in the plane.
    95. Edge list homomorphisms. (with P. Hell)
    96. Partitioning columns for secure distributed databases. (with V. Ganapathy, H. Garcia-Molina, R. Motwani, D. Thomas)
    97. Virus propagation in a graph. (with A. Saberi)
    98. On the graph turnpike problem. (with R. Motwani)
    99. 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.
    100. Is edge 3-colorability reconstructible? (with R. Motwani)
    101. List homomorphisms to balanced digraphs. (with P. Hell and A. Rafiey)
    102. Anonymizing graphs. (with S.U. Nabar and E. Terzi)
    103. List partitions to tridiagonal matrices. (with P. Hell and G. Schell)
    104. Approximating cover by 2K2-free bipartite graphs. (with E. Terzi)
    105. Some notes on nuf digraphs. (with P. Hell, B. Larose, C. Loten and C. Tardif)
    106. Graceful isometric embeddings of trees on n-cubes. (with C. Subi)
    107. On the complexity of MM1SNP. (with M. Bodirky and H. Chen)