Simon Mackenzie

Theoretical computer science

Simon
Mackenzie

Postdoctoral Fellow · UNSW Sydney
School of Computer Science and Engineering

Simon Mackenzie
On the job marketI’m looking for faculty, postdoctoral, and research positions starting in 2027. Get in touch

I work in complexity theory and algorithmic game theory, developing algorithms and proving lower bounds.

Much of my research is driven by longstanding questions in fair division and communication complexity.

Longstanding problems

Research now

I’m pursuing the interlacing programme in communication complexity, alongside current work in fair division, mechanism design, and approximate counting.

Recent preprints also answer questions on EF1 and Pareto optimality (Caragiannis et al., 2016) and truthful three-facility location (Lu et al., 2010).

Recent results and papers

About me

I’m a postdoc with Haris Aziz in UNSW’s Algorithmic Decision Theory (ADT) group. Previously, I held postdocs with Serge Gaspers at UNSW, Haris and Toby Walsh at CSIRO’s Data61, and Ariel Procaccia at Carnegie Mellon. I completed my PhD at UNSW with Serge and Toby.

Email Google Scholar DBLP X

01Selected contributions

Communication complexity

The interlacing programme

I’m pursuing the interlacing programme to tackle longstanding questions in communication complexity. Interlacing combines communication problems to control how much information must be exchanged, and in what order. With Abdallah Saffidine, I used it to refute the strongest form of the direct sum conjecture for total functions.

In a subsequent preprint with Serge Gaspers and Tao Zixu He, we extend this approach to prove that computing deterministic communication complexity from a truth table is NP-complete.

I’m currently exploring further extensions towards inapproximability.

Direct-sum paper · STOC 2025 NP-completeness preprint

Fair division · PhD research

Bounded envy-free cake cutting

Haris Aziz and I developed bounded protocols for dividing a cake so that no one prefers another person’s share. Our results for four agents and for any number of agents settled a longstanding problem. This work formed part of my PhD thesis, Upper Bounds for Cake Cutting, supervised by Serge Gaspers. I’m interested in determining the optimal query complexity of envy-free cake cutting, with matching upper and lower bounds.

Four-agent protocol · STOC 2016 General protocol · FOCS 2016 Cake-cutting overview · CACM 2020

Preprint · Fair division · 2026

An EFX counterexample you can check by hand

Hannaneh Akrami, Alexander Mayorov, Kurt Mehlhorn, Shreyas Srinivas, and Christoph Weidenbach first showed that envy-freeness up to any good (EFX) can fail for submodular valuations. Following their work, Mashbat Suzuki and I gave a different counterexample with three agents and eight goods that can be understood and checked by hand.

Our paper also gives a counterexample for approximate EFX with subadditive valuations. We have since combined our paper with theirs; these links are to the original preprints.

Our original EFX preprint

02Selected papers

All publications
  1. FOCS2016

    A discrete and bounded envy-free cake cutting protocol for any number of agents

    Haris Aziz, Simon Mackenzie

    A bounded protocol for dividing a cake among any number of agents so that no one prefers another person’s share, settling a longstanding question.

    arXiv Invited CACM article Quanta article
  2. STOC2025

    Refuting the Direct Sum Conjecture for Total Functions in Deterministic Communication Complexity

    Simon Mackenzie, Abdallah Saffidine

    Solving several instances together can require less deterministic communication than solving them separately. This gives a counterexample to the strongest form of the direct sum conjecture for total functions.

    arXiv Proceedings UNSW feature Formalisation by Beyond the Library
  3. Preprint2025

    NP-Completeness of Deterministic Communication Complexity via Relaxed Interlacing

    Serge Gaspers, Tao Zixu He, Simon Mackenzie

    Computing deterministic communication complexity from a truth table is NP-complete, answering a question raised by Yao in 1979.

    arXiv Interactive Lean proof inspector Lean source
  4. Preprint2026

    Counterexamples to EFX for Submodular and Subadditive Valuations

    Simon Mackenzie, Mashbat Suzuki

    Following the first nonexistence result of Akrami, Mayorov, Mehlhorn, Srinivas, and Weidenbach, we gave a different counterexample for submodular valuations that can be checked by hand, with three agents and eight goods.

    Original preprint; this work has since been combined with the paper by Akrami, Mayorov, Mehlhorn, Srinivas, and Weidenbach.

    arXiv Earlier SAT-based result

Recent results in fair division, apportionment, and mechanism design

My recent work resolves a conjecture in randomised apportionment, gives optimal subsidy bounds, combines fairness guarantees through randomisation, and answers questions about the limits of fair allocation and truthful mechanisms.

  1. Preprint2026

    Sampford Apportionment Satisfies Threshold Monotonicity

    Haris Aziz, Simon Mackenzie, Mashbat Suzuki

    Sampford apportionment satisfies threshold monotonicity, resolving a conjecture of Correa et al. (2024). A complementary theorem shows that, for seven or more parties, the separate pairwise threshold-monotonicity axiom is incompatible with quota and ex-ante proportionality.

    SSRN
  2. Preprint2026

    Optimal Subsidy Bounds for Goods and Chores: One Dollar Each Suffices

    Xinhang Lu, Simon Mackenzie, Mashbat Suzuki

    For additive utilities with item values between −1 and 1, we give a polynomial-time algorithm that eliminates envy using at most one unit of subsidy per agent. This bound is tight.

    Under review for the ACM-SIAM Symposium on Discrete Algorithms (SODA).

    arXiv
  3. Preprint2026

    Best-of-Both-Worlds Fairness for Mixed Goods and Chores

    Haris Aziz, Xiaolin Bu, Xinhang Lu, Simon Mackenzie, Mashbat Suzuki, Biaoshuai Tao, Toby Walsh

    For mixed goods and chores with additive utilities, we show how randomisation can combine envy-freeness in expectation with envy-freeness up to one item (EF1) in every realised allocation.

    Under review for the ACM-SIAM Symposium on Discrete Algorithms (SODA).

    arXiv
  4. Preprint2026

    When One Good Is Not Enough: EF1 and Pareto Optimality Are Not Compatible for Submodular Valuations

    Simon Mackenzie, Mashbat Suzuki

    EF1 and Pareto optimality can be incompatible for submodular valuations, even with two agents. This answers a question of Caragiannis et al. (2016).

    Under review for the International Conference on Web and Internet Economics (WINE).

    arXiv
  5. Preprint2026

    Anchoring for Truthfulness: The Random-Anchor Volume Mechanism for Multi-Facility Location

    Haris Aziz, Simon Mackenzie, Mashbat Suzuki

    A mechanism for three-facility location on the line that is strategyproof in expectation and gives a constant-factor approximation, answering a question of Lu, Sun, Wang and Zhu (2010).

    arXiv

Other recent work includes fair division of goods, chores, and cake (EC 2026, forthcoming) and exponential-time approximate counting (ESA 2026, forthcoming).

See all papers and preprints

03Background

Full CV

Academic and professional experience

  • 2024–2026
    UNSW SydneyResearch and teaching appointments
    Lecturer, COMP3821 · Term 3, 2026
    Postdoctoral Fellow · Haris Aziz · Feb–Dec 2026
    Lecturer, COMP9020 · Term 2, 2026
    Postdoctoral Fellow · Serge Gaspers · May–Sep 2024 and Aug–Dec 2025
  • 2022–2024
    Up and AtomScience communicator · Scriptwriting, animation, and field production
  • 2019–2022
    CSIRO’s Data61Postdoctoral Fellow · Haris Aziz and Toby Walsh
  • 2016–2018
    Carnegie Mellon UniversityPostdoctoral Fellow · Ariel Procaccia

04Media

Coverage of my research.

Further discussion

Computational Complexity blog Proof and Cake Envy

05Teaching & supervision

Teaching at UNSW

I teach computer science at UNSW, with a focus on mathematical foundations and algorithms.

  • Term 3, 2026
    Extended Algorithm Design and AnalysisCOMP3821 · Lecturer · UpcomingLectures and day-to-day course delivery; Serge Gaspers is lecturer in charge.
  • Term 2, 2026
    Foundations of Computer ScienceCOMP9020 · Lecturer
  • 2024, 2025
    Extended Algorithm Design and AnalysisCOMP3821 · Project supervisor and tutor
  • Algorithm Design and AnalysisCOMP3121 · Guest lecturer
  • Theory of Computer ScienceCOMP4141 · Tutor

Research supervision

I’ve supervised honours, master’s, and special research projects in communication complexity, fair division, and exponential-time algorithms.

  • Rayan Shahara Honours thesis · OXS valuations in fair division (provisional) · 2026
  • Tao Zixu He Honours thesis · NP-hardness of communication complexity · 2024–2025
  • Qi Wang Master’s thesis · Exponential-time approximate counting algorithms · 2024
  • Tao Zixu He Special research project · Measure and conquer for randomised algorithms · 2024

06Outreach

Working with Up and Atom

From 2022 to 2024, I worked with Up and Atom on scripts, storyboards, and Mathematica animations. I also worked on location at HATFest and the ITER research facility.

Selected videos

Get in touch.

Please get in touch about faculty, postdoctoral, or research positions, or if you’d like to collaborate.

School of Computer Science and Engineering
UNSW Sydney, Australia