EDBT 2026 Demo / reviewers in the wild / expert
Nir Shalmon
dblp:438/9135
· DBLP profile ↗
2ranked-venue papers
1as first author
2since 2021 · last 2026
0009-0000-5804-8312ORCID · corroborated
Domains — the database's venue-derived domains; a paper can count in several
Theory of computation · 2 · 1 first-author · 2 since 2021
Expertise — from the expertise taxonomy: the topics of the expert's papers under the CCF categories. A weight counts papers with recency: 1 for a paper about the topic, 0.3 when the topic is its context, halved every five years.
| Theoretical computer science
2 papers |
Computational complexity · 92% Computational geometry · 8% |
Topics — the 8 heaviest of 8, each with the papers that count most for it
| Topic | Weight | Papers | Last | Evidence papers |
|---|---|---|---|---|
Computational complexity
algebraic complexity |
2.0 | 2 | 2026 | Partial Derivative Complexity of a Product of Linearly Independent Quadratics · ICALP 2026 Rank Bounds and Polynomial-Time PIT for Σ^k Π Σ Π² Circuits · CCC 2026 |
Computational complexity › algebraic complexity
arithmetic circuit complexity |
1.0 | 1 | 2026 | Partial Derivative Complexity of a Product of Linearly Independent Quadratics · ICALP 2026 |
Computational complexity › circuit complexity › constant-depth circuits
depth-4 circuits |
1.0 | 1 | 2026 | Rank Bounds and Polynomial-Time PIT for Σ^k Π Σ Π² Circuits · CCC 2026 |
Computational complexity
lower bounds |
1.0 | 1 | 2026 | Partial Derivative Complexity of a Product of Linearly Independent Quadratics · ICALP 2026 |
Computational complexity › algebraic complexity › arithmetic formulas
multilinear formulas |
1.0 | 1 | 2026 | Partial Derivative Complexity of a Product of Linearly Independent Quadratics · ICALP 2026 |
Computational complexity › algebraic complexity
polynomial identity testing |
1.0 | 1 | 2026 | Rank Bounds and Polynomial-Time PIT for Σ^k Π Σ Π² Circuits · CCC 2026 |
Computational geometry
combinatorial geometry |
0.3 | 1 | 2026 | Rank Bounds and Polynomial-Time PIT for Σ^k Π Σ Π² Circuits · CCC 2026 |
Computational geometry › discrete geometry
sylvester-gallai theorem |
0.3 | 1 | 2026 | Rank Bounds and Polynomial-Time PIT for Σ^k Π Σ Π² Circuits · CCC 2026 |
Methods — techniques the papers use, named apart from their topics
wide algebras · 1.0rank analysis · 1.0jacobian method · 1.0hansen-type theorem · 1.0algebraic geometry · 1.0
| Year | Publication | Venue | Position |
|---|---|---|---|
| 2026 | Rank Bounds and Polynomial-Time PIT for Σ^k Π Σ Π² CircuitsabstractA depth-4 algebraic circuit with top fan-in k and bottom fan-in 2 is a circuit Φ of the form Φ = ∑_{i = 1}^k ∏_{j = 1}^{m_i} Q_{ij}, where the polynomials Q_{ij} ∈ 𝕂[x₁, …, x_n] have degree at most 2. The class of all such circuits is denoted by Σ^k Π Σ Π². We say that the circuit Φ is an identity if it formally computes the zero polynomial. An important parameter of Σ^k Π Σ Π² circuits Φ is their (linear) rank, which is defined as the vector space dimension of the polynomials {Q_{ij}}_{i ∈ [k], j ∈ [m_i]}. We prove that, when the base field 𝕂 is of characteristic zero, the rank of any (simple and minimal) Σ^k Π Σ Π² identity is upper bounded by a function which depends only on the top fan-in k. This result makes progress on [Beecken et al., 2013], being the first work to establish a bound on the rank of such identities that depends only on the top fan-in. Moreover, when combined with [Beecken et al., 2013], our main result yields the first deterministic, polynomial time PIT algorithm for Σ^k Π Σ Π² circuits. One of the key components of our proof of the rank bounds is the derivation of an approximate Hansen-type result, which is interesting in its own right. This result can be seen as an algebraic and higher-dimensional analogue of the approximate Sylvester-Gallai result of [Ai et al., 2014], and a distinct approximate fractional Sylvester-Gallai result than the one from [Garg et al., 2023]. Additionally, we prove a robust version of it, in the spirit of the generalization of Hansen’s theorem by [Boaz Barak et al., 2013]. This paper is an extended abstract of the full version of the paper, which can be found at [Garg et al., 2026]. Abhibhav Garg, Rafael Oliveira 0002, Akash Kumar Sengupta, Nir Shalmon, Amir Shpilka |
CCC | 4 |
| 2026 | Partial Derivative Complexity of a Product of Linearly Independent QuadraticsabstractThe partial derivative method is a central tool in algebraic complexity, underlying lower bounds for multilinear formulas, bounded depth circuits, and algebraic branching programs. A key feature of this measure is its subadditivity and submultiplicativity, which are usually used to upper bound the measure. However, proving lower bounds requires bounding the measure of explicit polynomials from below, and in some cases, a sharp estimate is required. For example, a frequently used fact is that the dimension of the space spanned by order k partial derivatives of a product of n linearly independent linear functions is binom(n,k). Beyond the linear case, however, not much is known about the behavior of the (general) partial derivative measure under multiplication. In particular, it has been conjectured that for algebraically independent polynomials g₁,… ,g_r ∈ ℂ[𝐱], the partial derivative complexity of the product ∏_{i=1}^r g_i(𝐱) grows exponentially with r (see [Chaugule et al., 2023]), but prior to this work such bounds were only known when the g_i’s are linear polynomials, or satisfy additional restrictions. In this paper, we show a lower bound of exp(Ω(r^{1/6})) for the measure of a product of r linearly independent quadratic polynomials. This is the first result to show such a lower bound on the partial derivative measure of a product of nonlinear polynomials, without any further restrictions. Interestingly, we only assume linear independence, which is weaker than algebraic independence. Our proof relies on algebraic-geometric and combinatorial techniques, combining the Jacobian approach of [Chaugule et al., 2023] together with the theory of wide algebras introduced in [Ananyan and Hochster, 2020; Oliveira and Sengupta, 2022; Garg et al., 2023]. To our knowledge, this is the first use of wide-algebra techniques for proving lower bounds on partial derivative complexity, and one of the first applications of these techniques outside the context of Sylvester-Gallai type problems. Nir Shalmon, Amir Shpilka |
ICALP | 1 |