VLDB 2026 Research / reviewers in the wild / expert
Mehrshad Taziki
dblp:361/6941
· DBLP profile ↗
2ranked-venue papers
0as first author
2since 2021 · last 2025
—ORCID · none
Domains — the database's venue-derived domains; a paper can count in several
Theory of computation · 2 · 2 since 2021
| Year | Publication | Venue | Position |
|---|---|---|---|
| 2025 | Dual Charging for Half-Integral TSP
Nathan Klein, Mehrshad Taziki |
APPROX/RANDOM | 2 |
| 2024 | Relative Fractional Independence NumberabstractWe define the “relative” fractional independence number of a graph$G$with respect to another graph$H$, as where the maximum is taken over all graphs$W$.,$G \boxtimes W$is the strong product of$G$and$W$, and$\alpha$denotes the independence number. We give a nontrivial linear program to compute$\alpha^{*}(G\vert H)$, and discuss some of its properties. We show that$\alpha^{*}(G\vert H) \geq \frac{X(G)}{X(H)}\geq-\frac{1}{\alpha^{*}(H\vert G)}$, where$X(G)$can be the independence number, the Shannon capacity, the fractional independence number, the Lovász number, or the Schrijver's or Szegedy's variants of the Lovász number of a graph$G$, This inequality is the first explicit nontrivial upper bound on the ratio of the invariants of two arbitrary graphs, as mentioned earlier, which can also be used to obtain upper or lower bounds for these invariants. As explicit applications, we present new upper bounds for the ratio of the Shannon capacity of two Cayley graphs and compute new lower bounds on the Shannon capacity of certain Johnson graphs (yielding the exact value of their Haemers number). Moreover, we show that$\alpha^{*}(G\vert H)$can be used to present a stronger version of the well-known No-Homomorphism Lemma. Sharareh Alipour, Amin Gohari, Mehrshad Taziki |
ITW | 3 |