Asaf Etgar

About

I'm a fifth year applied mathematics Ph.D candidate at Yale, where I'm fortunate to be advised by Anna Gilbert. My thesis is titled Estimate and Repair: Graph Algorithms for Limited and Corrupted Information. Previously, I completed my M.S. in computer science under the advisement of Nati Linial and my B.Sc. in mathematics, both at the Hebrew University of Jerusalem, Israel.

I am on the 2026–27 academic job market.

Research

I am interested in the theory and practice of graph algorithms, streaming algorithms, approximation algorithms and fixed-parameter algorithms. I focus on problems where the standard structural assumptions don't hold -- graphs that aren't metric, aren't complete, or whose key statistics cannot be known in advance.

Publications

• Metric repair is two problems: Which edges, and what weights (ALENEX 2027, to appear)
  • Asaf Etgar, Anna Gilbert arxiv code
• On the Connectivity and Diameter of Geodetic Graphs (European Journal of Combinatorics, 2024)
  • Asaf Etgar, Nati Linial journal arxiv
• The Effect of Information Content and Length on Name Recollection (ICPC 2022)
  • Asaf Etgar, Ram Friedman, Shaked Haiman, Dana Perez, Dror G. Feitelson IEEE Xplore

Preprints

• Structural Tractability Frontiers for Metric Repair (Submitted, 2026)
  • Asaf Etgar, Anna Gilbert, Jamie Tucker-Foltz arxiv
• Scalable Triangle Counting: The Threshold Algorithm (2026)
  • Asaf Etgar, Anna Gilbert, Quanquan C. Liu, Andrew McGregor arxiv code
• Parameter-Free Triangle Counting (Submitted, 2026)
  • Asaf Etgar, Anna Gilbert, Quanquan C. Liu, Andrew McGregor arxiv
• The F₂ Rank and Size of Graphs (2022)
  • Gal Beniamini, Asaf Etgar, Yael Kirkpatrick arxiv

Teaching

Yale

• Modern Combinatorics (MATH 3450), Part-Time Acting Instructor (Instructor of Record), co-taught with Richard Kenyon (Fall 2026)
• Multivariable Calculus (MATH S1190), Teaching Fellow, First-Year Scholars at Yale (Summers 2025, 2026)
• Discrete Mathematics (MATH 244), Teaching Fellow (Spring 2025)
• Intensive Algorithms (CPSC 366), Teaching Fellow (Springs 2024, 2026)

Hebrew University

• Calculus for CS Students (67559), Teaching Assistant & Course Developer (Spring 2022)
• Game Theory for High-School Students (67128), Instructor of Record & Course Developer, Federman Center for the Study of Rationality (Spring 2022)
• Data Structures (67109), Teaching Assistant (Fall 2020)

Service

• Research Mentor, Yale SUMRY Undergraduate Research Program (Summers 2023, 2026)
• Research Mentor, undergraduate research project in weighted random graph theory, co-supervised with Anna Gilbert (Summer 2025)
• Organizer, Graph Theory and Additive Combinatorics Reading Group, Yale University (Fall 2023)
• Reviewer: Journal of Graph Theory; ICLR