Sophie Huiberts
@sophie.huiberts.me
CNRS researcher in linear programming
Pinned
Beyond Smoothed Analysis: Analyzing the Simplex Method by the Book
Narrowing the gap between theory and practice is a longstanding goal of the algorithm analysis community. To further progress our understanding of how algorithms work in practice, we propose a new alg...
arxiv.org
The simplex algorithm is super efficient. 80 years of experience says it runs in linear time. Nobody can explain _why_ it is so fast.
We invented a new algorithm analysis framework to find out.
We invented a new algorithm analysis framework to find out.
Looking for inspiration for your #FOCS2025 pre-recorded talk? Check out this video youtu.be/Ygu5m-yPFhg
Producing recorded research talks
YouTube video by EATCS
youtu.be
November 15, 2025 at 11:01 AM
Looking for inspiration for your #FOCS2025 pre-recorded talk? Check out this video youtu.be/Ygu5m-yPFhg
Reposted by Sophie Huiberts
Update: yes.
In addition to their in-person talks, authors will have the option to upload a pre-recorded video, to be made available on the #FOCS2025 YouTube channel. Expect an email by the PC chairs shortly!
In addition to their in-person talks, authors will have the option to upload a pre-recorded video, to be made available on the #FOCS2025 YouTube channel. Expect an email by the PC chairs shortly!
November 15, 2025 at 12:25 AM
Update: yes.
In addition to their in-person talks, authors will have the option to upload a pre-recorded video, to be made available on the #FOCS2025 YouTube channel. Expect an email by the PC chairs shortly!
In addition to their in-person talks, authors will have the option to upload a pre-recorded video, to be made available on the #FOCS2025 YouTube channel. Expect an email by the PC chairs shortly!
Suppose you roll a skill check with disadvantage using two indistinguishable dice. Afterwards, you remember that disadvantage did not apply.
What can you roll to fix this situation fairly?
What can you roll to fix this situation fairly?
November 10, 2025 at 9:25 PM
Suppose you roll a skill check with disadvantage using two indistinguishable dice. Afterwards, you remember that disadvantage did not apply.
What can you roll to fix this situation fairly?
What can you roll to fix this situation fairly?
Do we know if @focs2025.bsky.social is doing video recordings this year?
November 10, 2025 at 12:36 PM
Do we know if @focs2025.bsky.social is doing video recordings this year?
Reposted by Sophie Huiberts
We uploaded a new version with links to Omer Reingold's "Research Life Stories", to Luca Trevisan's series of posts about gay and lesbian computer scientists, and so on.
Check out the updated version: eatcs.org/images/bulle...
The links are also in the comment below.
Happy reading!
Check out the updated version: eatcs.org/images/bulle...
The links are also in the comment below.
Happy reading!
November 10, 2025 at 8:20 AM
We uploaded a new version with links to Omer Reingold's "Research Life Stories", to Luca Trevisan's series of posts about gay and lesbian computer scientists, and so on.
Check out the updated version: eatcs.org/images/bulle...
The links are also in the comment below.
Happy reading!
Check out the updated version: eatcs.org/images/bulle...
The links are also in the comment below.
Happy reading!
Reposted by Sophie Huiberts
I wonder whether something similar can be done in the field of NP-hard problems, to obtain polynomial complexity results by similar (algorithmically mild) assumptions on scaling, perturbations, etc. This would shed light on why we are able to solve knapsack and TSP problems to very high dimension.
The simplex algorithm is super efficient. 80 years of experience says it runs in linear time. Nobody can explain _why_ it is so fast.
We invented a new algorithm analysis framework to find out.
We invented a new algorithm analysis framework to find out.
Beyond Smoothed Analysis: Analyzing the Simplex Method by the Book
Narrowing the gap between theory and practice is a longstanding goal of the algorithm analysis community. To further progress our understanding of how algorithms work in practice, we propose a new alg...
arxiv.org
November 7, 2025 at 10:07 AM
I wonder whether something similar can be done in the field of NP-hard problems, to obtain polynomial complexity results by similar (algorithmically mild) assumptions on scaling, perturbations, etc. This would shed light on why we are able to solve knapsack and TSP problems to very high dimension.
Reposted by Sophie Huiberts
Tell your friends! Warn your enemies! @mathandcobb.bsky.social will be sharing his take on Math in the Age of Social Media on Monday at the next @code4math.org Convening! Join the conversation on our Zulip:
code4math.zulipchat.com#narrow/chann...
code4math.zulipchat.com#narrow/chann...
November 6, 2025 at 4:57 PM
Tell your friends! Warn your enemies! @mathandcobb.bsky.social will be sharing his take on Math in the Age of Social Media on Monday at the next @code4math.org Convening! Join the conversation on our Zulip:
code4math.zulipchat.com#narrow/chann...
code4math.zulipchat.com#narrow/chann...
Reposted by Sophie Huiberts
Does there exist a commonly used public instance benchmark set for robust optimization? Or sets of instances which are frequently used within the literature?
November 6, 2025 at 10:48 PM
Does there exist a commonly used public instance benchmark set for robust optimization? Or sets of instances which are frequently used within the literature?
I hope that STOC is getting good money for their Google LLM collab
November 3, 2025 at 11:27 AM
I hope that STOC is getting good money for their Google LLM collab
speedrunners theoretical computer scientists
🤝
calling a milestone a "barrier"
🤝
calling a milestone a "barrier"
November 1, 2025 at 7:44 PM
speedrunners theoretical computer scientists
🤝
calling a milestone a "barrier"
🤝
calling a milestone a "barrier"
Reposted by Sophie Huiberts
Israel is obstructing aid deliveries to Gaza using a controversial new registration system for international NGOs, and in the first 12 days of the ceasefire, Israel had denied 99 requests to deliver aid to Gaza.
www.ft.com/content/676b...
www.ft.com/content/676b...
Israel still slowing aid deliveries into Gaza, humanitarian groups say
NGOs are being forced to re-register with authorities under new rules that require listing all Palestinian staff
www.ft.com
October 31, 2025 at 9:45 PM
Israel is obstructing aid deliveries to Gaza using a controversial new registration system for international NGOs, and in the first 12 days of the ceasefire, Israel had denied 99 requests to deliver aid to Gaza.
www.ft.com/content/676b...
www.ft.com/content/676b...
We have a call for contributions. Check out the text post on the channel for details.
Alongside the new bulletin, is the first video on the new EATCS Youtube channel!
We learn about different ways to record your seminar talks.
We learn about different ways to record your seminar talks.
October 31, 2025 at 12:13 PM
We have a call for contributions. Check out the text post on the channel for details.
Still got my head in the clouds about this. The paper is really out now 😍
The simplex algorithm is super efficient. 80 years of experience says it runs in linear time. Nobody can explain _why_ it is so fast.
We invented a new algorithm analysis framework to find out.
We invented a new algorithm analysis framework to find out.
Beyond Smoothed Analysis: Analyzing the Simplex Method by the Book
Narrowing the gap between theory and practice is a longstanding goal of the algorithm analysis community. To further progress our understanding of how algorithms work in practice, we propose a new alg...
arxiv.org
October 30, 2025 at 10:04 PM
Still got my head in the clouds about this. The paper is really out now 😍
Alongside the new bulletin, is the first video on the new EATCS Youtube channel!
We learn about different ways to record your seminar talks.
We learn about different ways to record your seminar talks.
October 30, 2025 at 8:12 PM
Alongside the new bulletin, is the first video on the new EATCS Youtube channel!
We learn about different ways to record your seminar talks.
We learn about different ways to record your seminar talks.
The recent popularity of PDHG algos for LP has been inspiring. Today FICO had a new release, shipping their own GPU-accelerated PDHG
This is a big moment for people to think about feasibility tolerances
This is a big moment for people to think about feasibility tolerances
October 28, 2025 at 1:21 PM
The recent popularity of PDHG algos for LP has been inspiring. Today FICO had a new release, shipping their own GPU-accelerated PDHG
This is a big moment for people to think about feasibility tolerances
This is a big moment for people to think about feasibility tolerances
Reposted by Sophie Huiberts
Interesting work on closing the gap between theory and practice of the simplex algorithm.
The simplex algorithm is super efficient. 80 years of experience says it runs in linear time. Nobody can explain _why_ it is so fast.
We invented a new algorithm analysis framework to find out.
We invented a new algorithm analysis framework to find out.
Beyond Smoothed Analysis: Analyzing the Simplex Method by the Book
Narrowing the gap between theory and practice is a longstanding goal of the algorithm analysis community. To further progress our understanding of how algorithms work in practice, we propose a new alg...
arxiv.org
October 28, 2025 at 5:11 AM
Interesting work on closing the gap between theory and practice of the simplex algorithm.
Reposted by Sophie Huiberts
!!
The simplex algorithm is super efficient. 80 years of experience says it runs in linear time. Nobody can explain _why_ it is so fast.
We invented a new algorithm analysis framework to find out.
We invented a new algorithm analysis framework to find out.
Beyond Smoothed Analysis: Analyzing the Simplex Method by the Book
Narrowing the gap between theory and practice is a longstanding goal of the algorithm analysis community. To further progress our understanding of how algorithms work in practice, we propose a new alg...
arxiv.org
October 27, 2025 at 12:48 PM
!!
Reposted by Sophie Huiberts
Good stuff. Scientific software and in particular optimization codes are everywhere, yet the magic sauce is often proprietary and found heuristically.
Analysis such as this one is net progress for the field.
Analysis such as this one is net progress for the field.
The simplex algorithm is super efficient. 80 years of experience says it runs in linear time. Nobody can explain _why_ it is so fast.
We invented a new algorithm analysis framework to find out.
We invented a new algorithm analysis framework to find out.
Beyond Smoothed Analysis: Analyzing the Simplex Method by the Book
Narrowing the gap between theory and practice is a longstanding goal of the algorithm analysis community. To further progress our understanding of how algorithms work in practice, we propose a new alg...
arxiv.org
October 27, 2025 at 10:12 AM
Good stuff. Scientific software and in particular optimization codes are everywhere, yet the magic sauce is often proprietary and found heuristically.
Analysis such as this one is net progress for the field.
Analysis such as this one is net progress for the field.
Reposted by Sophie Huiberts
Really really cool work! Instead of classic worst case analysis or next smoothed analysis, this now gives a linear bound on simplex algorithms _as implemented_!
We need more practical CS!
We need more practical CS!
Turns out, the textbooks are all wrong. State of the art LP software has ~5 tricks that differ from the textbook description. All good software uses the same 5 tricks!
Three of those tricks, we figured out how to make theoretical use of.
Three of those tricks, we figured out how to make theoretical use of.
October 27, 2025 at 8:28 AM
Really really cool work! Instead of classic worst case analysis or next smoothed analysis, this now gives a linear bound on simplex algorithms _as implemented_!
We need more practical CS!
We need more practical CS!
Reposted by Sophie Huiberts
I know what I'm reading on my train trip this week! Sophie and Eleon bridging the gap between analysis of algorithms and real-world computational optimization 🎉
The simplex algorithm is super efficient. 80 years of experience says it runs in linear time. Nobody can explain _why_ it is so fast.
We invented a new algorithm analysis framework to find out.
We invented a new algorithm analysis framework to find out.
Beyond Smoothed Analysis: Analyzing the Simplex Method by the Book
Narrowing the gap between theory and practice is a longstanding goal of the algorithm analysis community. To further progress our understanding of how algorithms work in practice, we propose a new alg...
arxiv.org
October 27, 2025 at 8:43 AM
I know what I'm reading on my train trip this week! Sophie and Eleon bridging the gap between analysis of algorithms and real-world computational optimization 🎉
The simplex algorithm is super efficient. 80 years of experience says it runs in linear time. Nobody can explain _why_ it is so fast.
We invented a new algorithm analysis framework to find out.
We invented a new algorithm analysis framework to find out.
Beyond Smoothed Analysis: Analyzing the Simplex Method by the Book
Narrowing the gap between theory and practice is a longstanding goal of the algorithm analysis community. To further progress our understanding of how algorithms work in practice, we propose a new alg...
arxiv.org
October 27, 2025 at 1:43 AM
The simplex algorithm is super efficient. 80 years of experience says it runs in linear time. Nobody can explain _why_ it is so fast.
We invented a new algorithm analysis framework to find out.
We invented a new algorithm analysis framework to find out.
if you can believe it, the recent smoothed analysis result was just happy byproduct from this research 👇
keep your eyes out for sunday's arxiv drop 👀 best paper i have ever written, maybe the best paper i will ever write
October 25, 2025 at 4:57 PM
if you can believe it, the recent smoothed analysis result was just happy byproduct from this research 👇
keep your eyes out for sunday's arxiv drop 👀 best paper i have ever written, maybe the best paper i will ever write
October 24, 2025 at 4:24 PM
keep your eyes out for sunday's arxiv drop 👀 best paper i have ever written, maybe the best paper i will ever write
i get to write an entire page bragging about my student and their awesome research?!
recommendation letter writing is fun
recommendation letter writing is fun
October 22, 2025 at 10:26 AM
i get to write an entire page bragging about my student and their awesome research?!
recommendation letter writing is fun
recommendation letter writing is fun
The challenge this year is GPU-accelerated primal heuristics. I am exciting to see what people will cook up!
The 2026 Land-Doig Competition is open! This year’s topic is GPU-Accelerated Primal Heuristics for Mixed-Integer Programming. Details below.
www.mixedinteger.org/2026/competi...
www.mixedinteger.org/2026/competi...
MIPcc26: The 2026 Land-Doig MIP Competition
www.mixedinteger.org
October 21, 2025 at 10:52 AM
The challenge this year is GPU-accelerated primal heuristics. I am exciting to see what people will cook up!