Julien Codsi

activity

20232026

most citedClassically Simulating Quantum Supremacy IQP Circuits through a Random Graph Approach

1 citations · 2 across the 13 of their papers we have counts for

collaborators

15 papers

math.CO2026

Tree-independence number VIII. 3PC-free graphs have logarithmic tree-independence number

Maria Chudnovsky, Julien Codsi, Ajaykrishnan E S +2

A three-path-configuration is a graph consisting of three pairwise internally vertex-disjoint paths, the union of every two of which is an induced cycle of length at least four. A…

math.CO2026

Excluding paths and bicliques

Maria Chudnovsky, Julien Codsi, Matjaž Krnc +1

Classes of graphs excluding a path and a biclique as induced subgraphs are extensively studied in the literature. One of the key structural results for such graphs is a Ramsey-type…

math.CO2026

Induced-Minor-Closed Classes have Linear, Square-Root, or Sub-Polynomial Tree-Independence

Maria Chudnovsky, Julien Codsi, Ajaykrishnan E S +1

An independent set in a graph $G$ is a set of pairwise non-adjacent vertices. A tree decomposition of $G$ is a pair $(T, χ)$ where $T$ is a tree and $χ : V (T) \to 2^{V (G)}$ …

math.CO2026

Coarse Balanced Separators in Biclique-Induced-Minor-Free Graphs

Maria Chudnovsky, Julien Codsi, Claire Kaneshiro

It is a classical theorem of Robertson and Seymour (1986) that the treewidth of a graph is linearly related to its separation number: the smallest integer $k$ such that, for every…

math.CO2026

Tree-independence number and forbidden induced subgraphs: excluding a $6$ -vertex path and a $(2, t)$ -biclique

Maria Chudnovsky, Julien Codsi, J. Pascal Gollin +2

We show that for every positive integer $t \geq 2$ there exists an integer $s$ such that every graph that contains no induced subgraph isomorphic to either the $6$ -vertex path or…

quant-ph2026

Unifying Graph Measures and Stabilizer Decompositions for the Classical Simulation of Quantum Circuits

Julien Codsi, Tuomas Laakkonen

Various algorithms have been developed to simulate quantum circuits on classical hardware. Among the most prominent are approaches based on \emph{stabilizer decompositions} and \em…

math.CO2026

Induced Minors and Coarse Tree Decompositions

Maria Chudnovsky, Julien Codsi, Ajaykrishnan E S +1

Let $G$ be a graph, $S \subseteq V (G)$ be a vertex set in $G$ and $r$ be a positive integer. The distance $r$ -independence number of $S$ is the size of the largest subset $I \subse…

math.CO2026

Extremal Graphs for the Lights Out Problem

Julien Codsi, Sergio Cristancho, Alexander Divoux +1

Lights Out is a game played on a graph $G$ where every vertex has a light bulb that is either on or off, and pressing a vertex $v$ toggles the state of every vertex in the closed n…

math.CO2025

Localized Erdős-Pósa Property for Subdivisions

Icey Siyi Ai, Maria Chudnovsky, Julien Codsi

For a graph $H$ , we say that $H$ has the Erdős-Pósa property for subdivisions with function $f$ , if, for every nonnegative integer $k$ and every graph $G$ , either $G$ contains (as…

math.CO2025

Induced minors and subpolynomial treewidth

Maria Chudnovsky, Julien Codsi, David Fischer +1

Given a family $H$ of graphs, we say that a graph $G$ is $H$ -induced-minor-free if no induced minor of $G$ is isomorphic to a member of $H$ , We denote…

math.CO2025

Tree-independence number VI. Thetas and pyramids

Maria Chudnovsky, Julien Codsi

Given a family $H$ of graphs, we say that a graph $G$ is $H$ -free if no induced subgraph of $G$ is isomorphic to a member of $H$ . Let $W_{t \times t}$ …

math.CO2025

Induced subgraphs and tree decompositions XIX. Thetas and forests

Maria Chudnovsky, Julien Codsi, Sepehr Hajebi +1

Let $H$ be a graph and let $C$ be a hereditary class of theta-free graphs such that $H \in / C$ . We prove that if (a) $H$ is a forest; and (b) $C$ exc…

math.CO2025

Tree independence number V. Walls and claws

Maria Chudnovsky, Julien Codsi, Daniel Lokshtanov +2

Given a family $H$ of graphs, we say that a graph $G$ is $H$ -free if no induced subgraph of $G$ is isomorphic to a member of $H$ . Let $S_{t, t, t}$ be t…

math.CO2024★ 1 cited

Counting independent sets in structured graphs

Matija Bucić, Maria Chudnovsky, Julien Codsi

Counting independent sets in graphs and hypergraphs under a variety of restrictions is a classical question with a long history. It is the subject of the celebrated container metho…

quant-ph2023★ 1 cited

Classically Simulating Quantum Supremacy IQP Circuits through a Random Graph Approach

Julien Codsi, John van de Wetering

Quantum Supremacy is a demonstration of a computation by a quantum computer that can not be performed by the best classical computer in a reasonable time. A well-studied approach t…

Tree-independence number VIII. 3PC-free graphs have logarithmic tree-independence number

Excluding paths and bicliques

Induced-Minor-Closed Classes have Linear, Square-Root, or Sub-Polynomial Tree-Independence

Coarse Balanced Separators in Biclique-Induced-Minor-Free Graphs

Tree-independence number and forbidden induced subgraphs: excluding a 6-vertex path and a (2,t)-biclique

Unifying Graph Measures and Stabilizer Decompositions for the Classical Simulation of Quantum Circuits

Induced Minors and Coarse Tree Decompositions

Extremal Graphs for the Lights Out Problem

Localized Erdős-Pósa Property for Subdivisions

Induced minors and subpolynomial treewidth

Tree-independence number VI. Thetas and pyramids

Induced subgraphs and tree decompositions XIX. Thetas and forests

Tree independence number V. Walls and claws

Counting independent sets in structured graphs

Classically Simulating Quantum Supremacy IQP Circuits through a Random Graph Approach

Tree-independence number and forbidden induced subgraphs: excluding a $6$ -vertex path and a $(2, t)$ -biclique