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.
  9. 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:

  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. A quadratic form for points in space, IBM Internal Note, 1993.
    17. Finding a vertex in a polytope, Bell Labs (with P. Vaidya).
    18. 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.
    19. The benefits of relaxing punctuality. (with R. Alur, T. Henzinger) Proc. 10th ACM Symp. on Principles of Distributed Computing (1991) 139-152.
    20. The benefits of relaxing punctuality. (with R. Alur, T. Henzinger) J. ACM 43 (1996) 116-146.
    21. Circuit switched link simulation: algorithms, complexity and implementation. (with A. Greenberg, V. Ramachandran, M. Rauch, L. Wang) (1992).
    22. Balanced Matroids. (with M. Mihail) Proc. 24th Ann. ACM Symp. on Theory of Computing (1992) 26-38.
    23. Monotone monadic SNP and constraint satisfaction. (with M. Vardi) Proc. 25th Ann. ACM Symp. on Theory of Computing (1993) 612-622.
    24. 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.
    25. A sublinear parallel algorithm for stable matching. (with N. Megiddo, S. Plotkin) Theoretical Computer Science 233 (2000) 297-308.
    26. A sublinear parallel algorithm for stable matching. (with N. Megiddo, S. Plotkin) Proc. 5th Ann. ACM-SIAM Symp. on Discrete Algorithms (1994) 632-637.
    27. Homomorphism closed vs. existential positive. (with M. Vardi) Logic in Comp. Sci. (2003), 311-320.
    28. Classification of homomorphisms to oriented cycles and k-partite satisfiability. SIAM J. Discrete Math 14 (2001) 471-480.
    29. List homomorphisms to reflexive graphs. (with P. Hell) J. Comb. Theory Series B 72-2 (1998) 236-250.
    30. List homomorphisms and circular arc graphs. (with P. Hell, J. Huang) Combinatorica 19-4 (1999) 487-505.
    31. Bi-arc graphs and the complexity of list homomorphisms (with P. Hell, J. Huang) J. Graph Theory 42 (1999) 61-80.
    32. The structure of bi-arc trees (with P. Hell, J. Huang) Discrete Math. 307 (2007) 393-401.
    33. List homomorphisms and retractions to reflexive digraphs. (with P. Hell, J. Huang)
    34. Complexity of graph partitions problems (with P. Hell, S. Klein, R. Motwani) Proc. 31st Ann. ACM Symp. on Theory of Computing (1999) 464-472.
    35. List partitions. (with P. Hell, S. Klein, R. Motwani) SIAM J. Discrete Mathematics 16 (2003) 449-478.
    36. Full constraint satisfaction problems. (with P. Hell) SIAM J. Computing. 36 (2006) 230-246.
    37. 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.
    38. Width one, bounded strict width, and chordal extensible graphs. (with P. Hell)
    39. List homomorphisms of graphs with bounded degrees. (with P. Hell, J. Huang) Discrete Math. 307 (2007) 386-392.
    40. Brooks type theorems for pair-list colourings and list homomorphisms. (with P. Hell, J. Huang) SIAM J. Discr. Math 22 (2008) 1-14.
    41. Extension problems with degree bounds. (with P. Hell, J. Huang) Discr. Appl. Math 157 (2009) 1592-1599.
    42. Acyclic homomorphisms and circular colorings of digraphs. (with P. Hell, B. Mohar) SIAM J. Discrete Math 17 (2003) 161-169.
    43. Digraph matrix partitions and trigraph homomorphisms. (with P. Hell, K. Tucker-Nally) Discrete Applied Math. 154 (2006) 2458-2469.
    44. List matrix partitions of chordal graphs. (with P. Hell, S. Klein, L.T. Nogueira, F. Protti). Latin Amer. Theor. Inform. (LATIN 2004) 100-108.
    45. List matrix partitions of chordal graphs. (with P. Hell, S. Klein, L.T. Nogueira, F. Protti). Theoretical Computer Science 349-1 (2005) 52-66.
    46. Matrix partitions of perfect graphs. (with P. Hell), Claude Berge Memorial Volume, Discrete Math. 306 (2006) 2450-2460.
    47. On realizations of point determining graphs, and obstructions to full homomorphisms. (with P. Hell) Discrete Mathematics 308 (2008), 1639-1652
    48. Two algorithms for general list matrix partitions. (with P. Hell, D. Kral, J. Sgall) SODA 2005, 870-876.
    49. Partition into k-vertex subgraphs of k-partite graphs. (with C. Subi) Electronic Colloquium on Computational Complexity (ECCC) TR06-016, 2006.
    50. Fanout limitations on constraint systems. Theoretical Computer Science 255 (2001) 281-293.
    51. 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).
    52. Online channel allocation in FDMA networks with reuse constraints. (with S. Shende) Information Processing Letters 67 (1998) 295-302.
    53. 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.
    54. Incremental clustering and dynamic information retrieval. (with M. Charikar, C. Chekuri, R. Motwani) SIAM J. Comput 33-6 (2004) 1417-1440.
    55. 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.
    56. Computing the median with uncertainty. (with R. Motwani, R. Panigrahy, C. Olston, J. Widom) SIAM J. Computing 32 (2003) 538-547.
    57. 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.
    58. Approximating the longest cycle problem in sparse graphs. (with R. Motwani, C. Subi) SIAM J. Computing. 31 (2002) 1596-1607.
    59. Web caching with request reordering. (with R. Motwani, R. Panigrahy, A. Zhu) Proc. 13th Ann. ACM-SIAM Symp. on Discrete Algorithms (2002) 104-105.
    60. 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.
    61. A combinatorial algorithm for MAX CSP. (with M. Datar, A. Gionis, R. Motwani, R. Panigrahy) Information Processing Letters 85 (2003) 307-315.
    62. Worst-case time bounds for coloring and satisfiability problems. (with R. Motwani) J. Algorithms 45 (2002) 192-201.
    63. Computing shortest paths with uncertainty. (with R. Motwani, L. O'Callaghan, C. Olston, R. Panigrahy) STACS 2003, 367-378.
    64. Computing shortest paths with uncertainty. (with R. Motwani, L. O'Callaghan, C. Olston, R. Panigrahy) J. Algorithms 62 (2007) 1-18.
    65. Representing graph metrics with fewest edges. (with A. Meyerson, R. Motwani, L. O'Callaghan, R. Panigrahy) STACS 2003, 355-366.
    66. Constraint satisfaction on finite groups with near subgroups, Electronic Colloquium on Computational Complexity (ECCC) TR05-005, 2005.
    67. Strong near subgroups and left gyrogroups. J. Algebra 259 (2003).
    68. Dichotomies for classes of homomorphism problems involving unary functions. (with F. Madelaine, I.A. Stewart) Theoretical Computer Science 314 (2004), 1-43.
    69. On Barnette's conjecture (weaker version). (with C. Subi)
    70. On Barnette's conjecture. (with C. Subi) Electronic Colloquium on Computational Complexity (ECCC) TR06-015, 2006.
    71. Disks on a tree: analysis of a combinatorial game. (with C. Subi) SIAM J. Discrete Math, 19-3 (2006), 543-552.
    72. 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.
    73. 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).
    74. Algorithms for multi-product pricing. ICALP 2004, 72-83 (with G. Aggarwal, R. Motwani, A. Zhu)
    75. A dichotomy theorem on fixed points of several nonexpansive mappings. SIAM J. Discrete Math 20-2 (2006) 291-301.
    76. Classification of bipartite boolean constraint satisfaction through delta-matroid intersection. (with D. Ford) Electronic Colloquium on Computational Complexity (ECCC) TR05-016, 2005.
    77. Classification of bipartite boolean constraint satisfaction through delta-matroid intersection. (with D. Ford) SIAM J. Discrete Math. 20-2 (2006) 372-394.
    78. Closures and dichotomies for quantified constraints. (with P. Kolaitis) Electronic Colloquium on Computational Complexity (ECCC) TR06-160, 2006.
    79. Algorithms for the database layout problem. (with G. Aggarwal, R. Motwani, R. Panigrahy, A. Zhu) ICDT 2005, 189-203.
    80. Anonimyzing tables. (with G. Aggarwal, K. Kenthapadi, R. Motwani, R. Panigrahy, D. Thomas, A. Zhu) ICDT 2005, 246-258.
    81. Approximation algorithms for k-anonymity. (with G. Aggarwal, K. Kenthapadi, R. Motwani, R. Panigrahy, D. Thomas, A. Zhu) JOPT (J. Privacy Technology) 2005.
    82. Finding large cycles in Hamiltonian graphs. (with R. Motwani) Symp. on Discr. Alg. (2005) 166-175.
    83. Finding large cycles in Hamiltonian graphs. (with R. Motwani) Electronic Colloquium on Computational Complexity (ECCC) TR06-156, 2006.
    84. Finding large cycles in Hamiltonian graphs. (with R. Motwani) Discrete Applied Math. 158 (2010) 882-893.
    85. 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.
    86. Achieving anonymity via clustering. (with G. Aggarwal, K. Kenthapadi, S. Khuller, R. Panigrahy, D. Thomas, A. Zhu) PODS 2006, 153-162.
    87. $k$-connected spanning subgraphs of low degree. (with R. Motwani, A. Zhu) Electronic Colloquium on Computational Complexity (ECCC) TR06-041, 2006.
    88. Generalized colourings (matrix partitions) of cographs. (with P. Hell, W. Hochstaettler)
    89. 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.
    90. List matrix partitions of interval graphs and its generalizations. (with P. Hell)
    91. Constraint satisfaction: a personal perspective (ps file) , (pdf file). Electronic Colloquium on Computational Complexity (ECCC) TR06-021, 2006.


    92. A practical computer program that diagnoses diseases in actual patients. (with C. Feder), Infinity publishing company, 117 pp.


    93. 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)


    94. Mini-Max procedure versus Bayes formula to calculate probability of a medical diagnosis. (with C. Feder)
    95. Best cost-benefit clinical data next to investigate at each diagnostic step. (with C. Feder)
    96. Artifice for databases that do not include all known diseases and clinical data. (with C. Feder)
    97. Complex clinical presentations and their models and clinical data. (with C. Feder)
    98. Simultaneous recommendation of best cost-benefit clinical data. (with C. Feder)
    99. Online algorithms for edge coloring. (with R. Motwani and R. Panigrahy)
    100. Matrix partitions with finitely many obstructions. (with P. Hell and W. Xie)
    101. Multi-domain bipartite Boolean constraint satisfaction and delta-matroids.
    102. Approximating Nash equilibria using small-support strategies. (with H. Nazerzadeh and A. Saberi) ACM Conference on Electronic Commerce (2007) 352-354.
    103. On quadrangles and convex figures in the plane.
    104. Edge list homomorphisms. (with P. Hell)
    105. Partitioning columns for secure distributed databases. (with V. Ganapathy, H. Garcia-Molina, R. Motwani, D. Thomas)
    106. Distributing data for secure database services. (with V. Ganapathy, H. Garcia-Molina, R. Motwani, D. Thomas) ICDT / EDBT 2011
    107. Distributing data for secure database services. (with V. Ganapathy, H. Garcia-Molina, R. Motwani, D. Thomas) Transactions on Data Privacy 5 (2012) 253-272
    108. Virus propagation in a graph. (with A. Saberi)
    109. Approximate pure equilibria in cut games. (with A. Asadpour and A. Saberi)
    110. Spanning trees and cuts. (with A. Asadpour and A. Saberi)
    111. On the graph turnpike problem. (with R. Motwani) Inform. Proc. Letters 109 (2009).
    112. 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.
    113. Nearly tight bounds on the number of Hamiltonian cycles of the hypercube and generalizations. (with C. Subi) Information Processing Letters 109 (2009), 267-272.
    114. Matchings and cycle decompositions in hypercubes. (with C. Subi)
    115. Is edge 3-colorability reconstructible? (with R. Motwani)
    116. List homomorphisms to balanced digraphs. (with P. Hell and A. Rafiey)
    117. Anonymizing graphs. (with S.U. Nabar and E. Terzi)
    118. Dichotomy for three-structured trigraph list homomorphism problems. (with P. Hell, D.G. Schell, and J. Stacho)
    119. Approximating the minimum chain completion problem. (with H. Mannila and E. Terzi)
    120. Graceful almost symmetrical trees. (with C. Subi)
    121. Graceful isometric embeddings of trees on n-cubes. (with C. Subi)
    122. Graceful labelings of paths on grids. (with C. Subi)
    123. On the complexity of MM1SNP. (with M. Bodirky and H. Chen)
    124. On the complexity of MMSNP. (with M. Bodirky and H. Chen) SIDMA 26 (2012) 404-414.
    125. An approximation algorithm for a scheduling problem. (with R. Motwani)
    126. Retractions to pseudoforests. (with P. Hell, P. Jonsson, A. Krokhin, and G. Nordh) SIAM J. on Discrete Math (SIDMA), 24-1 (2010).
    127. Interval graphs, adjusted interval digraphs,and reflexive list homomorphisms. (with P. Hell, J. Huang, and A. Rafiey) Discr. Appl. Math. 160 (2012) 697-707.
    128. Maximum gap labelings of graphs. (with C. Subi) Inform. Proc. Let., to appear.
    129. Minimum uniform gap labelings of trees. (with C. Subi)
    130. Hitting set, spanning trees, and the minimum length corridor problem. (with C. Subi)
    131. Embedding trees in Cartesian products by an edge. (with C. Subi)
    132. Homomorphic image d-cubes of d+1-cubes are retracts. (with C. Subi)
    133. Homomorphic image d-cubes of d+1-cubes are retracts (pdf) (with C. Subi)
    134. On hypercube labellings and antipodal monochromatic paths. Discr. Appl. Math. 161 (2013) 1421-1426 (with C. Subi)
    135. On monochromatic path and rainbow triangles in tournaments. (with C. Subi)
    136. Orthogonal matching decompositions of matching and Hamilton decompositions. (with C. Subi)
    137. Line graphs of cliques and clique minors. (with C. Subi)
    138. Packing edge-disjoint triangles into given graphs. Electronic Colloquium on Computational Complexity (ECCC) TR12-013, 2012. (with C. Subi)
    139. On 2 to the r, and (2 to the r)-1, dividing (3 to the s)-1. (with C. Subi)
    140. Irreducible polynomials for primes. (with C. Subi)
    141. Connected point determining obstructions. (with P. Hell)
    142. Obstructions to partitions of chordal graphs. (with P. Hell and S.N. Rizi) Discrete Mathematics 313 (2013) 1861-1871.
    143. Random dominating sets and Markov chains. (with P. Diaconis and A. Saberi)
    144. On graphs with many minimum cuts. (with S.O. Ghara and A. Saberi)
    145. On thinness of spanning trees in series-parallel and planar graphs. (with A. Saberi)
    146. Matrix partitions of split graphs. (with P. Hell and O. Shklarsky) CoRR abs/1306.1967 (2013).
    147. Matrix partitions of split graphs. (with P. Hell and O. Shklarsky) Discr. Appl. Math. 166 (2014), 91-96.
    148. 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 (2013) 1940-1963.
    149. Graphs admitting k-NU operations. Part 2: The irreflexive case. (with P. Hell, B. Larose, C. Loten, M. Siggers, and C. Tardif) SIAM J. Discr. Math 28 (2014) 817-834.
    150. Greedy versus optimum for the $k$-median problem. (with S. Ehsani and A. Saberi)
    151. On a conjecture of Erdos, Faber, and Lovasz. (with C. Subi)
    152. Partitioning graphs into l-walks. (with C. Subi)
    153. Edge-coloring almost bipartite multigraphs. (with C. Subi) Inform. Proc. Letters 113 (2013) 685-689.
    154. At most cubic caterpillars are not reconstructible from subtree data. (with C. Subi)
    155. On limit average degrees of iterated line graphs. (with C. Subi)
    156. Hamiltonian cycles for fixed distance graphs of the hypercube. (with C. Subi)
    157. Bipartite subgraphs of large odd girth series-parallel graphs. (with C. Subi)
    158. Pruning trees and tree reconstruction. (with C. Subi)
    159. Counting unions of sets. (with C. Subi)
    160. Mapping large odd girth cubic graphs to odd cycles. (with C. Subi)
    161. Steiner systems and near 2-factor decompositions. (with C. Subi)
    162. Colourings, homomorphisms and partitions of transitive digraphs. (with P. Hell and C. Hernandez Cruz)
    163. Complexity of corresponding homomorphisms. (with P. Hell)
    164. Distance-two colorings of Barnette graphs. (with P. Hell and C. Subi)
    165. Dichotomy for digraph homomorphism problems. (with A. Rafiey and J. Kinne)
    166. Matrix partitions of bipartite graphs. (with P. Hell and P. Valadkhan)
    167. Optimizing list homomorphisms of reflexive graphs. (with P. Hell and P. Valadkhan)