Nati Linial
List of publications from the DBLP Bibliography Server - FAQ
2009 | ||
---|---|---|
133 | EE | Nathan Linial, Adi Shraibman: Learning Complexity vs Communication Complexity. Combinatorics, Probability & Computing 18(1-2): 227-245 (2009) |
132 | EE | Nati Linial, Adi Shraibman: Lower bounds in communication complexity based on factorization norms. Random Struct. Algorithms 34(3): 368-394 (2009) |
2008 | ||
131 | EE | Nati Linial, Adi Shraibman: Learning Complexity vs. Communication Complexity. IEEE Conference on Computational Complexity 2008: 53-63 |
130 | EE | Nathan Linial, Jirí Matousek, Or Sheffet, Gábor Tardos: Graph Colouring with No Large Monochromatic Components. Combinatorics, Probability & Computing 17(4): 577-589 (2008) |
2007 | ||
129 | EE | Yael Dekel, James R. Lee, Nathan Linial: Eigenvectors of Random Graphs: Nodal Domains. APPROX-RANDOM 2007: 436-448 |
128 | EE | Nati Linial, Adi Shraibman: Lower bounds in communication complexity based on factorization norms. STOC 2007: 699-708 |
127 | EE | Nathan Linial, Jirí Matousek, Or Sheffet, Gábor Tardos: Graph coloring with no large monochromatic components. Electronic Notes in Discrete Mathematics 29: 115-122 (2007) |
126 | EE | Elon Portugaly, Nathan Linial, Michal Linial: EVEREST: a collection of evolutionary conserved protein domains. Nucleic Acids Research 35(Database-Issue): 241-246 (2007) |
2006 | ||
125 | EE | Nathan Linial, Roy Meshulam: Homological Connectivity Of Random 2-Complexes. Combinatorica 26(4): 475-487 (2006) |
124 | EE | Yonatan Bilu, Nathan Linial: Lifts, Discrepancy and Nearly Optimal Spectral Gap*. Combinatorica 26(5): 495-519 (2006) |
123 | EE | Alon Amit, Nathan Linial: Random Lifts of Graphs: Edge Expansion. Combinatorics, Probability & Computing 15(3): 317-332 (2006) |
122 | EE | Nathan Linial, Isabella Novik: How Neighborly Can a Centrally Symmetric Polytope Be? Discrete & Computational Geometry 36(2): 273-281 (2006) |
121 | EE | Nathan Linial, Michael E. Saks, David Statter: The Non-Crossing Graph. Electr. J. Comb. 13(1): (2006) |
120 | EE | Nathan Linial, Eran London: On the expansion rate of Margulis expanders. J. Comb. Theory, Ser. B 96(3): 436-442 (2006) |
119 | EE | Doron Lipson, Yonatan Aumann, Amir Ben-Dor, Nathan Linial, Zohar Yakhini: Efficient Calculation of Interval Scores for DNA Copy Number Data Analysis. Journal of Computational Biology 13(2): 215-228 (2006) |
118 | EE | Yotam Drier, Nathan Linial: Minors in lifts of graphs. Random Struct. Algorithms 29(2): 208-225 (2006) |
2005 | ||
117 | EE | Doron Lipson, Yonatan Aumann, Amir Ben-Dor, Nathan Linial, Zohar Yakhini: Efficient Calculation of Interval Scores for DNA Copy Number Data Analysis. RECOMB 2005: 83-100 |
116 | EE | Nathan Linial, Eyal Rozenman: Random Lifts Of Graphs: Perfekt Matchings. Combinatorica 25(4): 407-424 (2005) |
115 | EE | Yair Bartal, Nathan Linial, Manor Mendel, Assaf Naor: Some Low Distortion Metric Ramsey Problems. Discrete & Computational Geometry 33(1): 27-41 (2005) |
114 | EE | Nathan Linial, Jaikumar Radhakrishnan: Essential covers of the cube by hyperplanes. J. Comb. Theory, Ser. A 109(2): 331-338 (2005) |
113 | EE | Yonatan Bilu, Nathan Linial: Monotone maps, sphericity and bounded second eigenvalue. J. Comb. Theory, Ser. B 95(2): 283-299 (2005) |
112 | EE | Shlomo Hoory, Nathan Linial: A counterexample to a conjecture of Björner and Lovász on the chi-coloring complex. J. Comb. Theory, Ser. B 95(2): 346-349 (2005) |
111 | EE | Noam Kaplan, Ori Sasson, Uri Inbar, Moriah Friedlich, Menachem Fromer, Hillel Fleischer, Elon Portugaly, Nathan Linial, Michal Linial: ProtoNet 4.0: A hierarchical classification of one million protein sequences. Nucleic Acids Research 33(Database-Issue): 216-218 (2005) |
2004 | ||
110 | EE | Yonatan Bilu, Nathan Linial: Constructing Expander Graphs by 2-Lifts and Discrepancy vs. Spectral Gap. FOCS 2004: 404-412 |
109 | EE | Yonatan Bilu, Nathan Linial: Ramanujan Signing of Regular Graphs. Combinatorics, Probability & Computing 37(6): 911-912 (2004) |
108 | EE | Otfried Cheong, Sariel Har-Peled, Nathan Linial, Jirí Matousek: The One-Round Voronoi Game. Discrete & Computational Geometry 31(1): 125-138 (2004) |
107 | EE | Robert Krauthgamer, Nathan Linial, Avner Magen: Metric Embeddings--Beyond One-Dimensional Distortion. Discrete & Computational Geometry 31(3): 339-356 (2004) |
106 | EE | Yair Bartal, Nathan Linial, Manor Mendel, Assaf Naor: Low dimensional embeddings of ultrametrics. Eur. J. Comb. 25(1): 87-92 (2004) |
105 | EE | Shlomo Hoory, Nathan Linial: Colorings of the d-regular infinite tree. J. Comb. Theory, Ser. B 91(2): 161-167 (2004) |
2003 | ||
104 | EE | Yair Bartal, Nathan Linial, Manor Mendel, Assaf Naor: On metric ramsey-type phenomena. STOC 2003: 463-472 |
103 | EE | Nathan Linial, Michael E. Saks: The Euclidean Distortion of Complete Binary Trees. Discrete & Computational Geometry 29(1): 19-21 (2003) |
102 | Ori Sasson, Avishay Vaaknin, Hillel Fleischer, Elon Portugaly, Yonatan Bilu, Nathan Linial, Michal Linial: ProtoNet: hierarchical classification of the protein space. Nucleic Acids Research 31(1): 348-352 (2003) | |
2002 | ||
101 | Ori Sasson, Nathan Linial, Michal Linial: The metric space of proteins-comparative study of clustering algorithms. ISMB 2002: 14-21 | |
100 | EE | Nathan Linial, Avner Magen, Assaf Naor: Girth and euclidean distortion. STOC 2002: 705-711 |
99 | EE | Nathan Linial: Finite metric spaces: combinatorics, geometry and algorithms. Symposium on Computational Geometry 2002: 63 |
98 | EE | Otfried Cheong, Sariel Har-Peled, Nathan Linial, Jirí Matousek: The one-round Voronoi game. Symposium on Computational Geometry 2002: 97-101 |
97 | EE | Alon Amit, Nathan Linial: Random Graph Coverings I: General Theory and Graph Connectivity. Combinatorica 22(1): 1-18 (2002) |
96 | EE | Nathan Linial, Alex Samorodnitsky: Linear Codes and Character Sums. Combinatorica 22(4): 497-522 (2002) |
95 | EE | Noga Alon, Shlomo Hoory, Nathan Linial: The Moore Bound for Irregular Graphs. Graphs and Combinatorics 18(1): 53-57 (2002) |
94 | EE | Nathan Linial, Eyal Rozenman: An Extremal Problem on Degree Sequences of Graphs. Graphs and Combinatorics 18(3): 573-582 (2002) |
93 | EE | Alon Amit, Shlomo Hoory, Nathan Linial: A Continuous Analogue of the Girth Problem. J. Comb. Theory, Ser. B 84(2): 340-363 (2002) |
92 | Alon Amit, Nathan Linial, Jirí Matousek: Random lifts of graphs: Independence and chromatic number. Random Struct. Algorithms 20(1): 1-22 (2002) | |
2001 | ||
91 | EE | Alon Amit, Nathan Linial, Jirí Matousek, Eyal Rozenman: Random lifts of graphs. SODA 2001: 883-894 |
90 | EE | Danny Dolev, Yuval Harari, Nathan Linial, Noam Nisan, Michal Parnas: Neighborhood Preserving Hashing and Approximate Queries. SIAM J. Discrete Math. 15(1): 73-85 (2001) |
2000 | ||
89 | EE | Sanjeev Khanna, Nathan Linial, Shmuel Safra: On the Hardness of Approximating the Chromatic Number. Combinatorica 20(3): 393-415 (2000) |
88 | EE | Nathan Linial, Alex Samorodnitsky, Avi Wigderson: A Deterministic Strongly Polynomial Algorithm for Matrix Scaling and Approximate Permanents. Combinatorica 20(4): 545-568 (2000) |
87 | EE | Nathan Linial, Avner Magen: Least-Distortion Euclidean Embeddings of Graphs: Products of Cycles and Expanders. J. Comb. Theory, Ser. B 79(2): 157-171 (2000) |
86 | Golan Yona, Nathan Linial, Michal Linial: ProtoMap: automatic classification of protein sequences and hierarchy of protein families. Nucleic Acids Research 28(1): 49-55 (2000) | |
1999 | ||
85 | EE | Ran El-Yaniv, R. Kaniel, Nathan Linial: Competitive Optimal On-Line Leasing. Algorithmica 25(1): 116-140 (1999) |
84 | EE | Eyal Kushilevitz, Nathan Linial, Rafail Ostrovsky: The Linear-Array Conjecture in Communication Complexity Is False. Combinatorica 19(2): 241-254 (1999) |
83 | Amir Ben-Dor, Anna R. Karlin, Nathan Linial, Yuri Rabinovich: A Note on the Influence of an epsilon-Biased Random Source. J. Comput. Syst. Sci. 58(1): 174-176 (1999) | |
1998 | ||
82 | Golan Yona, Nathan Linial, Naftali Tishby, Michal Linial: A Map of the Protein Space: An Automatic Hierarchical Classification of all Protein Sequences. ISMB 1998: 212-221 | |
81 | EE | Nathan Linial, Avner Magen, Michael E. Saks: Trees and Euclidean Metrics. STOC 1998: 169-175 |
80 | EE | Nathan Linial, Alex Samorodnitsky, Avi Wigderson: A Deterministic Strongly Polynomial Algorithm for Matrix Scaling and Approximate Permanents. STOC 1998: 644-652 |
79 | EE | Nathan Linial, Ori Sasson: Non-Expansive Hashing. Combinatorica 18(1): 121-132 (1998) |
78 | Oded Goldreich, Shafi Goldwasser, Nathan Linial: Fault-Tolerant Computation in the Full Information Model. SIAM J. Comput. 27(2): 506-544 (1998) | |
1997 | ||
77 | Nathan Linial, Michael Luby, Michael E. Saks, David Zuckerman: Efficient Construction of a Small Hitting Set for Combinatorial Rectangles in High Dimension. Combinatorica 17(2): 215-234 (1997) | |
1996 | ||
76 | EE | Eyal Kushilevitz, Nathan Linial, Rafail Ostrovsky: The Linear-Array Conjecture in Communication Complexity is False. STOC 1996: 1-10 |
75 | EE | Nathan Linial, Ori Sasson: Non-Expansive Hashing. STOC 1996: 509-518 |
74 | Yossi Azar, Andrei Z. Broder, Anna R. Karlin, Nathan Linial, Steven Phillips: Biased Random Walks. Combinatorica 16(1): 1-18 (1996) | |
73 | Jeff Kahn, Nathan Linial, Alex Samorodnitsky: Inclusion-Exclusion: Exact and Approximate. Combinatorica 16(4): 465-477 (1996) | |
72 | EE | Shlomo Hoory, Nathan Linial: Central Points for Sets in Rn (or: the Chocolate Ice-Cream Problem). Discrete & Computational Geometry 15(4): 467-479 (1996) |
71 | EE | Eyal Kushilevitz, Nathan Linial, Yuri Rabinovich, Michael E. Saks: Witness Sets for Families of Binary Vectors. J. Comb. Theory, Ser. A 73(2): 376-380 (1996) |
1995 | ||
70 | Nathan Linial, Eran London, Yuri Rabinovich: The Geometry of Graphs and Some of its Algorithmic Applications. Combinatorica 15(2): 215-245 (1995) | |
69 | Jason Cooper, Nathan Linial: Fast Perfect-Information Leader-Election Protocols with Linear Immunity. Combinatorica 15(3): 319-332 (1995) | |
68 | Gil Kalai, Nathan Linial: On the distance distribution of codes. IEEE Transactions on Information Theory 41(5): 1467-1472 (1995) | |
1994 | ||
67 | Nathan Linial, Eran London, Yuri Rabinovich: The geometry of graphs and some of its algorithmic applications FOCS 1994: 577-591 | |
66 | Danny Dolev, Yuval Harari, Nathan Linial, Noam Nisan, Michal Parnas: Neighborhood Preserving Hashing and Approximate Queries. SODA 1994: 251-259 | |
65 | Craig Gotsman, Nathan Linial: Spectral Properties of Threshold Functions. Combinatorica 14(1): 35-50 (1994) | |
64 | EE | Nathan Linial, Yuri Rabinovich: Local and Global Clique Numbers. J. Comb. Theory, Ser. B 61(1): 5-15 (1994) |
1993 | ||
63 | Nathan Linial, David Peleg, Yuri Rabinovich, Michael E. Saks: Sphere Packing and Local Majorities in Graphs. ISTCS 1993: 141-149 | |
62 | Sanjeev Khanna, Nathan Linial, Shmuel Safra: On the Hardness of Approximating the Chromatic Number. ISTCS 1993: 250-260 | |
61 | EE | Nathan Linial, Michael Luby, Michael E. Saks, David Zuckerman: Efficient construction of a small hitting set for combinatorial rectangles in high dimension. STOC 1993: 258-267 |
60 | EE | Jason Cooper, Nathan Linial: Fast perfection-information leader-election protocol with linear immunity. STOC 1993: 662-671 |
59 | Miklós Ajtai, Nathan Linial: The influence of large coalitions. Combinatorica 13(2): 129-145 (1993) | |
58 | Nathan Linial, Michael E. Saks: Low diameter graph decompositions. Combinatorica 13(4): 441-454 (1993) | |
57 | Nathan Linial: Local-Global Phenomena in Graphs. Combinatorics, Probability & Computing 2: 491-503 (1993) | |
56 | Joel Friedman, Nathan Linial: On Convex Body Chasing. Discrete & Computational Geometry 9: 293-321 (1993) | |
55 | EE | Mauricio Karchmer, Nathan Linial, Ilan Newman, Michael E. Saks, Avi Wigderson: Combinatorial characterization of read-once formulae. Discrete Mathematics 114(1-3): 275-282 (1993) |
54 | Yitzhak Birk, Nathan Linial, Roy Meshulam: On the uniform-traffic capacity of single-hop interconnections employing shared directional multichannels. IEEE Transactions on Information Theory 39(1): 186- (1993) | |
53 | EE | Nathan Linial, Yishay Mansour, Noam Nisan: Constant Depth Circuits, Fourier Transform, and Learnability. J. ACM 40(3): 607-620 (1993) |
1992 | ||
52 | Yossi Azar, Andrei Z. Broder, Anna R. Karlin, Nathan Linial, Steven Phillips: Biased Random Walks STOC 1992: 1-9 | |
51 | EE | Allan Borodin, Nathan Linial, Michael E. Saks: An Optimal On-Line Algorithm for Metrical Task System. J. ACM 39(4): 745-763 (1992) |
50 | Noga Alon, Amotz Bar-Noy, Nathan Linial, David Peleg: Single Round Simulation on Radio Networks. J. Algorithms 13(2): 188-210 (1992) | |
49 | Craig Gotsman, Nathan Linial: The Equivalence of Two Problems on the Cube. J. Comb. Theory, Ser. A 61(1): 142-146 (1992) | |
48 | EE | François Jaeger, Nathan Linial, Charles Payan, Michael Tarsi: Group connectivity of graphs - A nonhomogeneous analogue of nowhere-zero flow properties. J. Comb. Theory, Ser. B 56(2): 165-182 (1992) |
47 | Nathan Linial: Locality in Distributed Graph Algorithms. SIAM J. Comput. 21(1): 193-201 (1992) | |
1991 | ||
46 | Oded Goldreich, Shafi Goldwasser, Nathan Linial: Fault-tolerant Computation in the Full Information Model (Extended Abstract) FOCS 1991: 447-457 | |
45 | Nathan Linial, Michael E. Saks: Decomposing Graphs into Regions of Small Diameter. SODA 1991: 320-330 | |
44 | Alok Aggarwal, Maria M. Klawe, David Lichtenstein, Nathan Linial, Avi Wigderson: A Lower Bound on the Area of Permutation Layouts. Algorithmica 6(2): 241-255 (1991) | |
43 | Jeff Kahn, Nathan Linial: Balancing extensions via Brunn-Minkowski. Combinatorica 11(4): 363-368 (1991) | |
42 | Nathan Linial, Yishay Mansour, Ronald L. Rivest: Results on Learnability and the Vapnik-Chervonenkis Dimension Inf. Comput. 90(1): 33-49 (1991) | |
41 | EE | Noga Alon, Nathan Linial, Roy Meshulam: Additive bases of vector spaces over prime fields. J. Comb. Theory, Ser. A 57(2): 203-210 (1991) |
40 | Noga Alon, Amotz Bar-Noy, Nathan Linial, David Peleg: A Lower Bound for Radio Broadcast. J. Comput. Syst. Sci. 43(2): 290-298 (1991) | |
1990 | ||
39 | Nathan Linial, Noam Nisan: Approximate Inclusion-Exclusion STOC 1990: 260-270 | |
38 | Nathan Linial, Noam Nisan: Approximate inclusion-exclusion. Combinatorica 10(4): 349-365 (1990) | |
37 | Baruch Awerbuch, Amotz Bar-Noy, Nathan Linial, David Peleg: Improved Routing Strategies with Succinct Tables. J. Algorithms 11(3): 307-341 (1990) | |
1989 | ||
36 | Nathan Linial, Umesh V. Vazirani: Graph Products and Chromatic Numbers FOCS 1989: 124-128 | |
35 | Nathan Linial, Yishay Mansour, Noam Nisan: Constant Depth Circuits, Fourier Transform, and Learnability FOCS 1989: 574-579 | |
34 | Noga Alon, Amotz Bar-Noy, Nathan Linial, David Peleg: On the Complexity of Radio Communication (Extended Abstract) STOC 1989: 274-285 | |
33 | Baruch Awerbuch, Amotz Bar-Noy, Nathan Linial, David Peleg: Compact Distributed Data Structures for Adaptive Routing (Extended Abstract) STOC 1989: 479-489 | |
32 | David Lichtenstein, Nathan Linial, Michael E. Saks: Some extremal problems arising form discrete control processes. Combinatorica 9(3): 269-287 (1989) | |
31 | EE | Noga Alon, Nathan Linial: Cycles of length 0 modulo k in directed graphs. J. Comb. Theory, Ser. B 47(1): 114-119 (1989) |
30 | Amotz Bar-Noy, Allan Borodin, Mauricio Karchmer, Nathan Linial, Michael Werman: Bounds on Universal Sequences. SIAM J. Comput. 18(2): 268-277 (1989) | |
1988 | ||
29 | EE | Nathan Linial, Yishay Mansour, Ronald L. Rivest: Results on Learnability and the Vapnick-Chervonenkis Dimension. COLT 1988: 56-68 |
28 | Nathan Linial, Yishay Mansour, Ronald L. Rivest: Results on learnability and the Vapnik-Chervonenkis dimension (Extended Abstract) FOCS 1988: 120-129 | |
27 | Jeff Kahn, Gil Kalai, Nathan Linial: The Influence of Variables on Boolean Functions (Extended Abstract) FOCS 1988: 68-80 | |
26 | Ron Aharoni, Paul Erdös, Nathan Linial: Optima of dual integer linear programs. Combinatorica 8(1): 13-20 (1988) | |
25 | Nathan Linial, László Lovász, Avi Wigderson: Rubber bands, convex embeddings and graph connectivity. Combinatorica 8(1): 91-102 (1988) | |
24 | EE | Nathan Linial, Roy Meshulam, Michael Tarsi: Matroidal bijections between graphs. J. Comb. Theory, Ser. B 45(1): 31-44 (1988) |
1987 | ||
23 | Nathan Linial: Distributive Graph Algorithms-Global Solutions from Local Data FOCS 1987: 331-335 | |
22 | David Lichtenstein, Nathan Linial, Michael E. Saks: Imperfect Random Sources and Discrete Controlled Processes STOC 1987: 169-177 | |
21 | Allan Borodin, Nathan Linial, Michael E. Saks: An Optimal Online Algorithm for Metrical Task Systems STOC 1987: 373-382 | |
20 | EE | Paul Erdös, Nathan Linial, Shlomo Moran: Extremal problems on permutations under cyclic equivalence. Discrete Mathematics 64(1): 1-11 (1987) |
1986 | ||
19 | Nathan Linial, László Lovász, Avi Wigderson: A Physical Interpretation of Graph Connectivity, and Its Algorithmic Applications FOCS 1986: 39-48 | |
18 | Nathan Linial: Legal coloring of graphs. Combinatorica 6(1): 49-54 (1986) | |
17 | EE | Nathan Linial: Graph coloring and monotone functions on posets. Discrete Mathematics 58(1): 97-98 (1986) |
16 | EE | Ron Aharoni, Nathan Linial: Minimal non-two-colorable hypergraphs and minimal unsatisfiable formulas. J. Comb. Theory, Ser. A 43(2): 196-204 (1986) |
1985 | ||
15 | Alok Aggarwal, Maria M. Klawe, David Lichtenstein, Nathan Linial, Avi Wigderson: Multi-Layer Grid Embeddings FOCS 1985: 186-196 | |
14 | Michael Ben-Or, Nathan Linial: Collective Coin Flipping, Robust Voting Schemes and Minima of Banzhaf Values FOCS 1985: 408-416 | |
13 | Ron Aharoni, Paul Erdös, Nathan Linial: Dual Integer Linear Programs and the Relationship between their Optima STOC 1985: 476-483 | |
12 | Nathan Linial, Michael E. Saks: Searching Ordered Structures. J. Algorithms 6(1): 86-103 (1985) | |
11 | Nathan Linial: Every Poset Has a Central Element. J. Comb. Theory, Ser. A 40(2): 195-210 (1985) | |
10 | Nathan Linial, Michael Tarsi: Deciding Hypergraph 2-Colourability by H-Resolution. Theor. Comput. Sci. 38: 343-347 (1985) | |
1984 | ||
9 | EE | Nathan Linial: Graph decompositions without isolates. J. Comb. Theory, Ser. B 36(1): 16-25 (1984) |
8 | Nathan Linial: The Information-Theoretic Bound is Good for Merging. SIAM J. Comput. 13(4): 795-801 (1984) | |
1983 | ||
7 | Nathan Linial: Legal Coloring of Graphs FOCS 1983: 470-472 | |
6 | Nathan Linial, Michael E. Saks: Information Bounds Are Good for Search Problems on Ordered Data Structures FOCS 1983: 473-475 | |
5 | Nathan Linial, Michael E. Saks, Vera T. Sós: Largest digraphs contained in all n-tournaments. Combinatorica 3(1): 101-104 (1983) | |
1982 | ||
4 | Nathan Linial: A New Derivation of the Counting Formula for Young Tableaux. J. Comb. Theory, Ser. A 33(3): 340-342 (1982) | |
3 | Nathan Linial, Michael Tarsi: The Counterfeit Coin Problem Revisited. SIAM J. Comput. 11(3): 409-415 (1982) | |
1981 | ||
2 | EE | Nathan Linial: On Petersen's graph theorem. Discrete Mathematics 33(1): 53-56 (1981) |
1 | Nathan Linial: Extending the Greene-Kleitman Theorem to Directed Graphs. J. Comb. Theory, Ser. A 30(3): 331-334 (1981) |