Publications

Conferences · Journals · Thesis

2026

  1. Circuit Diameter of Polyhedra is Strongly Polynomial 
    Bento Natura
  2. Trust Region Interior Point Methods: Optimal ℓ2\ell_2- and Faster Wide-Neighborhood Path Following 
    Daniel Dadush, Haoyuan Ma, Bento Natura, and László A. Végh

2024

  1. A Strongly Polynomial Algorithm for Linear Programs with at Most Two Non-Zero Entries per Row or Column 
    Full versions: Part I (initialization & bit complexity) on arXiv; Part II (straight line complexity bound) in preparation.

2022

  1. Interior Point Methods Are Not Worse than Simplex 
  2. On Circuit Diameter Bounds via Circuit Imbalances 
  3. A Faster Interior-Point Method for Sum-of-Squares Optimization 
    Shunhua Jiang, Bento Natura, and Omri Weinstein
  4. Circuit Imbalance Measures and Linear Programming 
    Farbod Ekbatani, Bento Natura, and László A. Végh
  5. The Pareto Cover Problem 
    Bento Natura, Meike Neuwohner, and Stefan Weltge

2021

  1. An Accelerated Newton-Dinkelbach Method and Its Application to Two Variables per Inequality Systems 

2020

  1. A Scaling-Invariant Algorithm for Linear Programming Whose Running Time Depends Only on the Constraint Matrix 
  2. Revisiting Tardos's Framework for Linear Programming: Faster Exact Solutions using Approximate Solvers 
    Daniel Dadush, Bento Natura, and László A. Végh

2019

  1. Global Interconnect Optimization 
    Siad Daboul, Stephan Held, Bento Natura, and Daniel Rotter

Thesis

  1. Exact Linear Programming: Circuits, Curvature, and Diameter 
    Bento Natura
    London School of Economics and Political Science, 2022