Theoretical computer science

Ariel Sapir

PhD student Bar-Ilan University

Hi! I’m a fourth-year PhD student in the Department of Computer Science and Artificial intelligence at Bar-Ilan University, supervised by Prof. Liam Roditty.

I’m interested in graph algorithms, particularly approximated shortest paths, spanners, emulators and dynamic graphs. One of my goals is understanding: How do algorithms and achievable approximation guarantees differ between weighted and unweighted graphs?

Previously, I completed my MSc in Computer Science at Ben-Gurion University of the Negev, where I worked on distributed graph coloring in the LOCAL model under the supervision of Prof. Michael Elkin. I also received my BSc in Mathematics and Computer Science from Ben-Gurion University, with a concentration in mathematical logic and axiomatic set theory.

Ariel Sapir — a portrait made of graphs A relaxed portrait formed from circular vertices and connecting edges. Vertices match the text colour; edges use a contrasting colour for the selected theme. The space between them is transparent.

Publications

Background

Education

  • 2023–present

    PhD in Computer Science · In progress

    Bar-Ilan University

    Approximate shortest paths, spanners and emulators in static and dynamic graphs, with an emphasis on the differences between weighted and unweighted settings. Supervised by Prof. Liam Roditty.

  • 2015–2018

    MSc in Computer Science

    Ben-Gurion University of the Negev

    Distributed graph coloring in the LOCAL model, where both the number of colors and the round complexity depend on the graph’s arboricity. Supervised by Prof. Michael Elkin.

  • 2010–2014

    BSc in Mathematics and Computer Science

    Ben-Gurion University of the Negev

    Mathematics major with a minor in Computer Science. Most degree credits were earned through “Project 100” (later known as the Euler Program), a program for high-achieving highschool students taking BSc mathematics courses.

Experience

  • Oct 2024–present

    Head Teaching Assistant

    Bar-Ilan University · Computer Science and Artificial Intelligence

    Updating exercise slides and overseeing homework assignments for Probability for Computer Science in both fall and spring semesters. Coordination between lecturers, teaching assistants and assignment graders.

  • Dec 2023–present

    Academic Tutor

    Bar-Ilan University · Computer Science and Artificial Intelligence

    Tutoring theoretical computer science and mathematics courses for computer science students serving in the military reserves.

  • Sep 2021–Aug 2023

    Algorithmic Researcher

    Ribbon Communications · CTO Group

    Modeling real-world networking problems as graph-theoretic flow problems, designing and implementing efficient algorithms, and benchmarking them on real-world service-provider networks, both locally and worldwide.

  • Oct 2015–Aug 2021

    Information Systems Engineer

    Israeli Navy · Mamtam

    Design and documentation of information systems, including role-based interfaces, integrations with external systems, and analysis of operational requirements.

  • Mar 2015–Aug 2017

    Teaching Assistant

    Ben-Gurion University of the Negev · Computer Science

    TAing for Design of Algorithms and Automata and Formal Languages, guiding computer science students through theoretical concepts and problem solving.

Theses

MSc thesis · 2018

Distributed Graph Coloring

Ben-Gurion University of the Negev · Supervised by Prof. Michael Elkin

In a distributed graph, vertices coordinate their colors through local communication rounds such that adjacent vertices receive different colors. A standard goal is to use Δ + 1 colors, where Δ is the maximum degree of the graph. We instead focus on a number of colors that depends on the graph’s arboricity a. We extend our results to partial coloring and list coloring.

PhD thesis · In progress

Doctoral dissertation

Bar-Ilan University · Supervised by Prof. Liam Roditty

I’ll add the dissertation here when it’s available. It will cover several topics related to shortest paths, w.h.p.

Seminars

Teaching

Teaching assistantships

Courses I have taught as a teaching assistant, with the semesters listed below.

Free Time

Outside research, I enjoy designing board games and anime fansubbing of opening and ending songs, including translation and karaoke timing.

I also developed Pokémon Orange, a browser game built entirely with HTML and JavaScript. My friends and I drew all of its artwork by hand (=mouse) in MS Paint.

Document

Loading… Download

Talk

Open in new tab