No photo of Nati Linial

View Scopus Profile

Nati Linial

Former affiliation
 https://orcid.org/0000-0002-0918-3136
    Calculated based on number of publications stored in Pure and citations from Scopus
    1976 …2025

    Research activity per year

    Filter
    Conference contribution

    Search results

    • 2021

      An improved protocol for the exactly-N problem

      Linial, N. & Shraibman, A., 1 Jul 2021, 36th Computational Complexity Conference, CCC 2021. Kabanets, V. (ed.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, p. 2:1-2:8 8 p. 2. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 200).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      2 Scopus citations
    • 2020

      Functional Evolutionary Modeling Exposes Overlooked Protein-Coding Genes Involved in Cancer

      Brandes, N., Linial, N. & Linial, M., 2020, Bioinformatics Research and Applications - 16th International Symposium, ISBRA 2020, Proceedings. Cai, Z., Mandoiu, I., Narasimhan, G., Skums, P. & Guo, X. (eds.). Springer, p. 119-126 8 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 12304 LNBI).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

    • PWAS: Proteome-wide association study

      Brandes, N., Linial, N. & Linial, M., 2020, Research in Computational Molecular Biology - 24th Annual International Conference, RECOMB 2020, Proceedings. Schwartz, R. (ed.). Springer, p. 237-239 3 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 12074 LNBI).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      1 Scopus citations
    • 2019

      Expander graphs-both local and global

      Chapman, M., Linial, N. & Peled, Y., Nov 2019, Proceedings - 2019 IEEE 60th Annual Symposium on Foundations of Computer Science, FOCS 2019. IEEE Computer Society, p. 158-170 13 p. 8948700. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS; vol. 2019-November).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      Open Access

    • On the communication complexity of high-dimensional permutations

      Linial, N., Pitassi, T. & Shraibman, A., 1 Jan 2019, 10th Innovations in Theoretical Computer Science, ITCS 2019. Blum, A. (ed.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 54. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 124).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      7 Scopus citations
    • 2014

      From average case complexity to improper learning complexity

      Daniely, A., Linial, N. & Shalev-Shwartz, S., 2014, STOC 2014 - Proceedings of the 2014 ACM Symposium on Theory of Computing. Association for Computing Machinery, p. 441-448 8 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      Open Access
      70 Scopus citations
    • 2013

      On the practically interesting instances of MAXCUT

      Bilu, Y., Daniely, A., Linial, N. & Saks, M., 2013, 30th International Symposium on Theoretical Aspects of Computer Science, STACS 2013. p. 526-537 12 p. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 20).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      17 Scopus citations
    • 2012

      No justified complaints: On fair sharing of multiple resources

      Dolev, D., Feitelson, D. G., Halpern, J. Y., Kupferman, R. & Linial, N., 2012, ITCS 2012 - Innovations in Theoretical Computer Science Conference. p. 68-75 8 p. (ITCS 2012 - Innovations in Theoretical Computer Science Conference).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      104 Scopus citations
    • 2011

      Geometric Interpretation of Gene Expression by Sparse Reconstruction of Transcript Profiles

      Prat, Y., Fromer, M., Linial, M. & Linial, N., 2011, Research in Computational Molecular Biology - 15th Annual International Conference, RECOMB 2011, Proceedings. Bafna, V. & Sahinalp, S. C. (eds.). Springer Verlag, p. 355-357 3 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 6577 LNBI).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

    • Oblivious collaboration

      Afek, Y., Babichenko, Y., Feige, U., Gafni, E., Linial, N. & Sudakov, B., 2011, Distributed Computing - 25th International Symposium, DISC 2011, Proceedings. p. 489-504 16 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 6950 LNCS).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      4 Scopus citations

    • The dynamics of reputation systems

      Ban, A. & Linial, N., 2011, TARK XIII: Theoretical Aspects of Rationality and Knowledge - Proceedings of the 13th Conference, TARK 2011. p. 91-100 10 p. (ACM International Conference Proceeding Series).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      5 Scopus citations
    • 2010

      Are Stable Instances Easy?

      Bilu, Y. & Linial, N., 2010, Innovations in Computer Science - ICS 2010 . Tsinghua University Press, p. 332-341 10 p.

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

    • 2008

      Learning complexity vs. communication complexity

      Linial, N. & Shraibman, A., 2008, Proceedings - 23rd Annual IEEE Conference on Computational Complexity, CCC 2008. p. 53-63 11 p. 4558809. (Proceedings of the Annual IEEE Conference on Computational Complexity).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      Open Access
      12 Scopus citations
    • 2007

      Eigenvectors of random graphs: Nodal domains

      Dekel, Y., Lee, J. R. & Linial, N., 2007, Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 10th International Workshop, APPROX 2007 and 11th International Workshop, RANDOM 2007, Proceedings. Springer Verlag, p. 436-448 13 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 4627 LNCS).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      7 Scopus citations

    • Lower bounds in communication complexity based on factorization norms

      Linial, N. & Shraibman, A., 2007, STOC'07: Proceedings of the 39th Annual ACM Symposium on Theory of Computing. p. 699-708 10 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      31 Scopus citations
    • 2002

      Finite metric-spaces---combinatorics, geometry and algorithms

      Linial, N., 2002, Proceedings of the International Congress of Mathematicians (Beijing, 2002). Higher Education Press, Vol. III. p. 573-586 14 p.

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

    • 2001

      Random lifts of graphs

      Amit, A., Linial, N., Matoušek, J. & Rozenman, E., 2001, Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms. p. 883-894 12 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      23 Scopus citations
    • 1998

      A map of the protein space - An automatic hierarchical classification of all protein sequences

      Yona, G., Linial, N., Tishby, N. & Linial, M., 1998, Proceedings of the 6th International Conference on Intelligent Systems for Molecular Biology, ISMB 1998. AAAI Press, p. 212-221 10 p. (Proceedings of the 6th International Conference on Intelligent Systems for Molecular Biology, ISMB 1998).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      26 Scopus citations
    • 1996

      Non-expansive hashing

      Linial, N. & Sasson, O., 1 Jul 1996, Proceedings of the 28th Annual ACM Symposium on Theory of Computing, STOC 1996. Association for Computing Machinery, p. 509-518 10 p. (Proceedings of the Annual ACM Symposium on Theory of Computing; vol. Part F129452).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      Open Access
      23 Scopus citations

    • The linear-array conjecture in communication complexity is false

      Kushilevitz, E., Linial, N. & Ostrovsky, R., 1 Jul 1996, Proceedings of the 28th Annual ACM Symposium on Theory of Computing, STOC 1996. Association for Computing Machinery, p. 1-10 10 p. (Proceedings of the Annual ACM Symposium on Theory of Computing; vol. Part F129452).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      2 Scopus citations
    • 1994

      Neighborhood preserving hashing and approximate queries

      Dolev, D., Harari, Y., Linial, N., Nisan, N. & Parnas, M., 1994, Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms. Publ by ACM, p. 251-259 9 p. (Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      15 Scopus citations
    • 1993

      Efficient construction of a small hitting set for combinatorial rectangles in high dimension

      Linial, N., Luby, M., Saks, M. & Zuckerman, D., 1 Jun 1993, Proceedings of the 25th Annual ACM Symposium on Theory of Computing, STOC 1993. Association for Computing Machinery, p. 258-267 10 p. (Proceedings of the Annual ACM Symposium on Theory of Computing; vol. Part F129585).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      Open Access
      8 Scopus citations

    • Fast perfect-information leader-election protocol with linear immunity

      Cooper, J. & Linial, N., 1 Jun 1993, Proceedings of the 25th Annual ACM Symposium on Theory of Computing, STOC 1993. Association for Computing Machinery, p. 662-671 10 p. (Proceedings of the Annual ACM Symposium on Theory of Computing; vol. Part F129585).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      Open Access
      9 Scopus citations

    • On the Hardness of Approximating the Chromatic Number.

      Khanna, S., Linial, N. & Safra, S., 1993, 2nd Israel Symposium on Theory and Computing Systems: ISTCS 1993. IEEE Computer Society, p. 250-260 11 p.

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

    • Sphere Packing and Local Majorities in Graphs.

      Linial, N., Peleg, D., Rabinovich, Y. & Saks, M. E., 1993, 2nd Israel Symposium on Theory and Computing Systems: ISTCS 1993. IEEE Computer Society, p. 141-149 9 p.

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      Open Access
    • 1992

      Biased random walks

      Azar, Y., Broder, A. Z., Karlin, A. R., Linial, N. & Phillips, S., 1 Jul 1992, Proceedings of the 24th Annual ACM Symposium on Theory of Computing, STOC 1992. Association for Computing Machinery, p. 1-9 9 p. (Proceedings of the Annual ACM Symposium on Theory of Computing; vol. Part F129722).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      20 Scopus citations
    • 1991

      Decomposing graphs into regions of small diameter

      Linial, N. & Saks, M., 1 Mar 1991, Proceedings of the 2nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1991. Association for Computing Machinery, p. 320-330 11 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      51 Scopus citations

    • Fault-tolerant computation in the full information model

      Goldreich, O., Goldwasser, S. & Linial, N., Dec 1991, Annual Symposium on Foundations of Computer Science (Proceedings). Publ by IEEE, p. 447-457 11 p. (Annual Symposium on Foundations of Computer Science (Proceedings)).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      18 Scopus citations
    • 1990

      Approximate Inclusion-Exclusion

      Linial, N. & Nisan, N., 1990, Proc 22nd Annu ACM Symp Theory Comput. Publ by ACM, p. 260-270 11 p. (Proc 22nd Annu ACM Symp Theory Comput).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      Open Access
      7 Scopus citations
    • 1989

      Compact distributed data structures for adaptive routing

      Awerbuch, B., Bar-Noy, A., Linial, N. & Peleg, D., 1989, Proc Twenty First Annu ACM Symp Theory Comput. Publ by ACM, p. 479-489 11 p. (Proc Twenty First Annu ACM Symp Theory Comput).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      Open Access
      66 Scopus citations

    • Constant depth circuits, Fourier transform, and learnability

      Linial, N., Mansour, Y. & Nisan, N., 1989, Annual Symposium on Foundations of Computer Science (Proceedings). Publ by IEEE, p. 574-579 6 p. (Annual Symposium on Foundations of Computer Science (Proceedings)).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      69 Scopus citations

    • Graph products and chromatic numbers

      Linial, N. & Vazirani, U., 1989, Annual Symposium on Foundations of Computer Science (Proceedings). Publ by IEEE, p. 124-128 5 p. (Annual Symposium on Foundations of Computer Science (Proceedings)).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      26 Scopus citations

    • On the complexity of radio communication

      Alon, N., Bar-Noy, A., Linial, N. & Peleg, D., 1989, Proc Twenty First Annu ACM Symp Theory Comput. Publ by ACM, p. 274-285 12 p. (Proc Twenty First Annu ACM Symp Theory Comput).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      Open Access
      32 Scopus citations
    • 1988

      Collective Coin Flipping and Other Models of Imperfect Randomness

      Benor, M., Linial, N. & Saks, M., 1988, Combinatorics /. Hajnal, A., Lovasz, L. & Sos, V. (eds.). p. 75-112 38 p. ( Colloquia mathematica Societatis Janos Bolyai ; vol. 52).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

    • Influence of variables on Boolean functions

      Kahn, J., Kalai, G. & Linial, N., 1988, Annual Symposium on Foundations of Computer Science (Proceedings). Publ by IEEE, p. 68-80 13 p. (Annual Symposium on Foundations of Computer Science (Proceedings)).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      510 Scopus citations

    • Results on learnability and the Vapnik-Chervonenkis dimension

      Linial, N., Mansour, Y. & Rivest, R. L., 1988, Annual Symposium on Foundations of Computer Science (Proceedings). Publ by IEEE, p. 120-129 10 p. (Annual Symposium on Foundations of Computer Science (Proceedings)).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      12 Scopus citations
    • 1987

      An Optimal Online Algorithm for Metrical Task Systems

      Borodin, A., Linial, N. & Saks, M. E., 1987, Proceedings of the 19th Annual ACM Symposium on Theory of Computing, STOC 1987. p. 373-382 10 p.

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      60 Scopus citations

    • DISTRIBUTIVE GRAPH ALGORITHMS-GLOBAL SOLUTIONS FROM LOCAL DATA.

      Linial, N., 1987, Annual Symposium on Foundations of Computer Science (Proceedings). IEEE, p. 331-335 5 p. (Annual Symposium on Foundations of Computer Science (Proceedings)).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      142 Scopus citations
    • 1986

      PHYSICAL INTERPRETATION OF GRAPH CONNECTIVITY, AND ITS ALGORITHMIC APPLICATIONS.

      Linial, N., Lovasz, L. & Wigderson, A., 1986, Annual Symposium on Foundations of Computer Science (Proceedings). IEEE, p. 39-48 10 p. (Annual Symposium on Foundations of Computer Science (Proceedings)).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      7 Scopus citations
    • 1985

      COLLECTIVE COIN FLIPPING, ROBUST VOTING SCHEMES AND MINIMA OF BANZHAF VALUES.

      Ben-Or, M. & Linial, N., 1985, Annual Symposium on Foundations of Computer Science (Proceedings). IEEE, p. 408-416 9 p. (Annual Symposium on Foundations of Computer Science (Proceedings)).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      106 Scopus citations

    • DUAL INTEGER LINEAR PROGRAMS AND THE RELATIONSHIP BETWEEN THEIR OPTIMA.

      Aharoni, R., Erdos, P. & Linial, N., 1985, Conference Proceedings of the Annual ACM Symposium on Theory of Computing. ACM (Order n 508850), p. 476-483 8 p. (Conference Proceedings of the Annual ACM Symposium on Theory of Computing).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      9 Scopus citations

    • MULTI-LAYER GRID EMBEDDINGS.

      Aggarwal, A., Klawe, M., Lichtenstein, D., Linial, N. & Wigderson, A., 1985, Annual Symposium on Foundations of Computer Science (Proceedings). IEEE, p. 186-196 11 p. (Annual Symposium on Foundations of Computer Science (Proceedings)).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      11 Scopus citations
    • 1983

      INFORMATION BOUNDS ARE GOOD FOR SEARCH PROBLEMS ON ORDERED DATA STRUCTURES.

      Linial, N. & Saks, M. E., 1983, Annual Symposium on Foundations of Computer Science (Proceedings). IEEE, p. 473-475 3 p. (Annual Symposium on Foundations of Computer Science (Proceedings)).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      7 Scopus citations

    • LEGAL COLORING OF GRAPHS.

      Linial, N., 1983, Annual Symposium on Foundations of Computer Science (Proceedings). IEEE, p. 470-472 3 p. (Annual Symposium on Foundations of Computer Science (Proceedings)).

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

      6 Scopus citations
    Your message has successfully been sent.
    Your message was not sent due to an error.