Cohen Gil

Research output

Research output per year 2012 2015 2016 2024

• 31 Conference contribution
• 8 Article
• 2 Meeting Abstract

Research output per year

Research output per year

Search results

• 2024

  Asymptotically-Good RLCCs with (log n)²⁺o(1) Queries

  Cohen, G. & Yankovitz, T., Jul 2024, 39th Computational Complexity Conference, CCC 2024. Santhanam, R. (ed.). 8. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 300).

  Tel Aviv University

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

• Tight Bounds for the Zig-Zag Product

  Cohen, G., Cohen, I. & Maor, G., 2024, Proceedings - 2024 IEEE 65th Annual Symposium on Foundations of Computer Science, FOCS 2024. IEEE Computer Society, p. 1470-1499 30 p. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS).

  Tel Aviv University

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

  Approximating Iterated Multiplication of Stochastic Matrices in Small Space

  Cohen, G., Doron, D., Sberlo, O. & Ta-Shma, A., 2 Jun 2023, STOC 2023 - Proceedings of the 55th Annual ACM Symposium on Theory of Computing. Saha, B. & Servedio, R. A. (eds.). p. 35-45 11 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

  Tel Aviv University, Ben-Gurion University of the Negev

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

  Open Access

  • Computer science 100%
  • Machinery 95%
  • Polynomials 77%

• Random Walks on Rotating Expanders

  Cohen, G. & Maor, G., 2 Jun 2023, STOC 2023 - Proceedings of the 55th Annual ACM Symposium on Theory of Computing. Saha, B. & Servedio, R. A. (eds.). p. 971-984 14 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

  Tel Aviv University

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

  Open Access

  • Computer science 100%
  • Costs 38%

• Spectral Expanding Expanders

  Cohen, G. & Cohen, I., Jul 2023, 38th Computational Complexity Conference, CCC 2023. Ta-Shma, A. (ed.). 8. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 264).

  Tel Aviv University

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

  • Eigenvalues and eigenfunctions 100%
  • Parallel algorithms 89%
  • Topology 64%
• 2022

  Expander Random Walks: The General Case and Limitations

  Cohen, G., Minzer, D., Peleg, S., Potechin, A. & Ta-Shma, A., 1 Jul 2022, 49th EATCS International Conference on Automata, Languages, and Programming, ICALP 2022. Bojanczyk, M., Merelli, E. & Woodruff, D. P. (eds.). 43. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 229).

  Tel Aviv University

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

  • Labeling 100%
  • Networks (circuits) 56%

• Explicit binary tree codes with sub-logarithmic size alphabet

  Ben Yaacov, I., Cohen, G. & Yankovitz, T., 6 Sep 2022, STOC 2022 - Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing. Leonardi, S. & Gupta, A. (eds.). p. 595-608 14 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

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

  • Binary trees 100%
  • Color 57%

• LCC and LDC: Tailor-Made Distance Amplification and a Refined Separation

  Cohen, G. & Yankovitz, T., 1 Jul 2022, 49th EATCS International Conference on Automata, Languages, and Programming, ICALP 2022. Bojanczyk, M., Merelli, E. & Woodruff, D. P. (eds.). 44. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 229).

  Tel Aviv University

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

  • Amplification 100%
  • Polynomials 50%

• Relaxed Locally Decodable and Correctable Codes: Beyond Tensoring

  Cohen, G. & Yankovitz, T., 2022, Proceedings - 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science, FOCS 2022. IEEE Computer Society, p. 24-35 12 p. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS; vol. 2022-October).

  Tel Aviv University

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

  • Tensors 100%
  • Deterioration 45%
• 2021

  Candidate tree codes via pascal determinant cubes

  Yaacov, I. B., Cohen, G. & Narayanan, A. K., 1 Sep 2021, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2021. Wootters, M. & Sanita, L. (eds.). 54. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 207).

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

  • Geometry 100%

• Error reduction for weighted PRGs against read once branching programs

  Cohen, G., Doron, D., Renard, O., Sberlo, O. & Ta-Shma, A., 1 Jul 2021, 36th Computational Complexity Conference, CCC 2021. Kabanets, V. (ed.). 22. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 200).

  Tel Aviv University

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

  • Seed 100%

• Expander random walks: A Fourier-analytic approach

  Cohen, G., Peri, N. & Ta-Shma, A., 15 Jun 2021, STOC 2021 - Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing. Khuller, S. & Williams, V. V. (eds.). p. 1643-1655 13 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

  Tel Aviv University

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

  • Physics 100%
  • Communication 57%
  • Markov chains 56%
  • Labels 49%
  • Computational complexity 47%

• Rate amplification and query-efficient distance amplification for linear LCC and LDC

  Cohen, G. & Yankovitz, T., 1 Jul 2021, 36th Computational Complexity Conference, CCC 2021. Kabanets, V. (ed.). 1. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 200).

  Tel Aviv University

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

  • Amplification 100%
• 2020

  Palette-alternating tree codes

  Cohen, G. & Samocha, S., 1 Jul 2020, 35th Computational Complexity Conference, CCC 2020. Saraf, S. (ed.). 11. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 169).

  Tel Aviv University

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

  • Color 100%
  • Binary trees 34%
  • Coloring 32%
  • Communication 13%

• Pseudorandom pseudo-distributions with near-optimal error for read-once branching programs

  BRAVERMAN, MARK., COHEN, GIL. & GARG, SUMEGHA., 2020, In: SIAM Journal on Computing. 49, 5

  Tel Aviv University

  Research output: Contribution to journal › Article › peer-review

  • Branching Programs 100%
  • Hitting Set 79%
  • Pseudorandom Generator 79%
  • Seed 75%
  • Derandomization 40%
• 2019

  Two-source condensers with low error and small entropy gap via entropy-resilient functions

  Ben-Aroya, A., Cohen, G., Doron, D. & Ta-Shma, A., 1 Sep 2019, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2019. Achlioptas, D. & Vegh, L. A. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 43. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 145).

  Tel Aviv University

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

  • Entropy 100%
  • Polynomials 30%
• 2018

  Explicit binary tree codes with polylogarithmic size alphabet

  Cohen, G., Haeupler, B. & Schulman, L. J., 20 Jun 2018, STOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing. Henzinger, M., Kempe, D. & Diakonikolas, I. (eds.). p. 1074-1087 14 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

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

  • Binary trees 100%
  • Polynomials 31%

• Hitting sets with near-Optimal error for read-Once branching programs

  Braverman, M., Cohen, G. & Garg, S., 20 Jun 2018, STOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing. Henzinger, M., Kempe, D. & Diakonikolas, I. (eds.). p. 940-951 12 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

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

  • Seed 100%
  • Probability distributions 30%
• 2017

  On the degree of univariate polynomials over the integers

  Cohen, G., Shpilka, A. & Tal, A., 1 Jun 2017, In: Combinatorica. 37, 3, p. 419-464 46 p.

  Tel Aviv University

  Research output: Contribution to journal › Article › peer-review

  • Univariate 100%
  • Polynomial 60%
  • Integer 59%
  • Threshold Phenomena 24%
  • Lattice Theory 21%

• Towards optimal two-source extractors and ramsey graphs

  Cohen, G., 19 Jun 2017, STOC 2017 - Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing. McKenzie, P., King, V. & Hatami, H. (eds.). p. 1157-1170 14 p. (Proceedings of the Annual ACM Symposium on Theory of Computing; vol. Part F128415).

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

  • Entropy 100%
• 2016

  Bi-Lipschitz bijection between the Boolean cube and the Hamming ball

  Benjamini, I., Cohen, G. & Shinkar, I., 1 May 2016, In: Israel Journal of Mathematics. 212, 2, p. 677-703 27 p.

  Weizmann Institute of Science

  Research output: Contribution to journal › Article › peer-review

  • Sampling Distribution 100%
  • Bijection 84%
  • Regular hexahedron 82%
  • Lipschitz 72%
  • Ball 69%

• Extractors for Near Logarithmic Min-Entropy

  Cohen, G. & Schulman, L. J., 14 Dec 2016, Proceedings - 57th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2016. IEEE Computer Society, p. 178-187 10 p. 7782930. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS; vol. 2016-December).

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

  • Entropy 100%
  • Bins 14%

• Local correlation breakers and applications to three-source extractors and mergers

  Cohen, G., 2016, In: SIAM Journal on Computing. 45, 4, p. 1297-1338 42 p.

  Research output: Contribution to journal › Article › peer-review

  • Mergers 100%
  • Extractor 94%
  • Random variables 69%
  • Entropy 34%
  • Random variable 26%

• Making the Most of Advice: New Correlation Breakers and Their Applications

  Cohen, G., 14 Dec 2016, Proceedings - 57th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2016. IEEE Computer Society, p. 188-196 9 p. 7782931. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS; vol. 2016-December).

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

  • Entropy 100%
  • Random variables 81%
  • Seed 40%
  • Amplification 20%

• Non-malleable extractors - New tools and improved constructions

  Cohen, G., 1 May 2016, 31st Conference on Computational Complexity, CCC 2016. Raz, R. (ed.). p. 8:1-8:29 (Leibniz International Proceedings in Informatics, LIPIcs; vol. 50).

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

  • Seed 100%
  • Entropy 71%

• Privacy Amplification Against Active Quantum Adversaries

  Cohen, G. & Vidick, T., 22 Aug 2016, (Submitted) In: arxiv.org. 26 p.

  Research output: Contribution to journal › Article

  • Amplification 100%
  • Communication 9%

• Quantum-Proof Extractors: Optimal up to Constant Factors

  Chung, K-M., Cohen, G., Vidick, T. & Wu, X., 13 May 2016, In: arxiv.org. 23 p.

  Research output: Contribution to journal › Article

  • Entropy 100%
  • Seed 81%
  • Amplification 40%
  • Sampling 27%

• The complexity of DNF of parities

  Cohen, G. & Shinkar, I., 14 Jan 2016, ITCS 2016 - Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science. p. 47-58 12 p. (ITCS 2016 - Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science).

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

  Open Access

  • Parity 100%
  • Symmetric Functions 51%
  • Lower bound 43%
  • Decision tree 42%
  • Polynomial 25%

• Two-source dispersers for polylogarithmic entropy and improved Ramsey graphs

  Cohen, G., 19 Jun 2016, STOC 2016 - Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing. Mansour, Y. & Wichs, D. (eds.). p. 278-284 7 p. (Proceedings of the Annual ACM Symposium on Theory of Computing; vol. 19-21-June-2016).

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

  Open Access

  • Entropy 100%
  • Computer science 39%
• 2015

  Local Correlation Breakers and Applications to Three-Source Extractors and Mergers

  Cohen, G., 11 Dec 2015, Proceedings - 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015. IEEE Computer Society, p. 845-862 18 p. 7354431. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS; vol. 2015-December).

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

  • Random variables 100%
  • Seed 25%

• On Rigid Matrices and U-Polynomials

  Alon, N. & Cohen, G., 1 Dec 2015, In: Computational Complexity. 24, 4, p. 851-879 29 p.

  Tel Aviv University, Weizmann Institute of Science

  Research output: Contribution to journal › Article › peer-review

  • Hitting Set 100%
  • Polynomial 57%
  • Expander 46%
  • Class 32%
  • Alternatives 22%

• Two structural results for low degree polynomials and applications

  Cohen, G. & Tal, A., 1 Aug 2015, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 18th International Workshop, APPROX 2015, and 19th International Workshop, RANDOM 2015. Garg, N., Jansen, K., Rao, A. & Rolim, J. D. P. (eds.). p. 680-709 30 p. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 40).

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

  • Polynomials 100%

• Zero-fixing extractors for sub-logarithmic entropy

  Cohen, G. & Shinkar, I., 2015, Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Proceedings. Halldorsson, M. M., Kobayashi, N., Speckmann, B. & Iwama, K. (eds.). p. 343-354 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 9134).

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

  • Extractor 100%
  • Entropy 60%
  • Logarithmic 60%
  • Zero 36%
  • Output 17%

• Zero-Fixing Extractors for Sub-Logarithmic Entropy

  Cohen, G. & Shinkar, I., 2015, In: Automata, Languages, and Programming, Pt I. 9134, p. 343-354 12 p.

  Weizmann Institute of Science

  Research output: Contribution to journal › Meeting Abstract › peer-review

  • Extractor 100%
  • Entropy 60%
  • Logarithmic 60%
  • Zero 36%
  • Output 17%
• 2014

  Nonmalleable extractors with short seeds and applications to privacy amplification

  Cohen, G., Raz, R. & Segev, G., 2014, In: SIAM Journal on Computing. 43, 2, p. 450-476 27 p.

  Weizmann Institute of Science, The Hebrew University of Jerusalem

  Research output: Contribution to journal › Article › peer-review

  • Extractor 100%
  • Privacy 92%
  • Amplification 88%
  • Seed 74%
  • Entropy 34%

• Two sides of the coin problem

  Cohen, G., Ganor, A. & Raz, R., 1 Sep 2014, Leibniz International Proceedings in Informatics, LIPIcs. Jansen, K., Rolim, J. D. P., Devanur, N. R. & Moore, C. (eds.). p. 618-629 12 p. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 28).

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

  • Networks (circuits) 100%
• 2013

  Efficient multiparty protocols via log-depth threshold formulae (Extended abstract)

  Cohen, G., Damgård, I. B., Ishai, Y., Kölker, J., Miltersen, P. B., Raz, R. & Rothblum, R. D., 2013, Advances in Cryptology, CRYPTO 2013 - 33rd Annual Cryptology Conference, Proceedings. PART 2 ed. p. 185-202 18 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 8043 LNCS, no. PART 2).

  Technion - Israel Institute of Technology

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

  Open Access

  • Distributed computer systems 100%
  • Threshold Function 80%
  • Cryptography 78%
  • Logarithmic 53%
  • Multiparty Computation 50%

• On rigid matrices and U-polynomials

  Alon, N. & Cohen, G., 2013, Proceedings - 2013 IEEE Conference on Computational Complexity, CCC 2013. p. 197-206 10 p. 6597762. (Proceedings of the Annual IEEE Conference on Computational Complexity).

  Tel Aviv University

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

  • Hitting Set 100%
  • Polynomials 84%
  • Polynomial 57%
  • Expander 46%
  • Class 32%
• 2012

  Non-malleable extractors with short seeds and applications to privacy amplification

  Cohen, G., Raz, R. & Segev, G., 2012, Proceedings - 2012 IEEE 27th Conference on Computational Complexity, CCC 2012. p. 298-308 11 p. 6243406. (Proceedings of the Annual IEEE Conference on Computational Complexity).

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

  • Extractor 100%
  • Privacy 92%
  • Amplification 88%
  • Seed 74%
  • Entropy 50%

• Non-Malleable Extractors with Short Seeds and Applications to Privacy Amplification

  Cohen, G., Raz, R. & Segev, G., 2012, In: 2012 Ieee 27Th Annual Conference On Computational Complexity (Ccc). p. 298-308 11 p.

  Weizmann Institute of Science

  Research output: Contribution to journal › Meeting Abstract › peer-review

  • Extractor 100%
  • Privacy 92%
  • Amplification 88%
  • Seed 74%
  • Entropy 20%

• On the degree of univariate polynomials over the integers

  Cohen, G., Shpilka, A. & Tal, A., 2012, ITCS 2012 - Innovations in Theoretical Computer Science Conference. p. 409-427 19 p. (ITCS 2012 - Innovations in Theoretical Computer Science Conference).

  Technion - Israel Institute of Technology

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

  • Univariate 100%
  • Polynomial 60%
  • Integer 59%
  • Threshold Phenomena 24%
  • Lattice Theory 21%