Demo Data from EDBT 2026 / reviewers in the wild / expert
Daniel Kleber
dblp:426/8318
· DBLP profile ↗
1ranked-venue papers
0as first author
1since 2021 · last 2026
—ORCID · none
Domains — the database's venue-derived domains; a paper can count in several
Theory of computation · 1 · 1 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
1 paper |
Computational complexity · 100% |
Topics — the 4 heaviest of 4, each with the papers that count most for it
| Topic | Weight | Papers | Last | Evidence papers |
|---|---|---|---|---|
Computational complexity
circuit complexity |
1.0 | 1 | 2026 | Optimal Depth-Three Circuits for Inner Product · CCC 2026 |
Computational complexity › circuit complexity
circuit lower bounds |
1.0 | 1 | 2026 | Optimal Depth-Three Circuits for Inner Product · CCC 2026 |
Computational complexity › algebraic complexity › arithmetic circuit complexity
depth-3 circuit |
1.0 | 1 | 2026 | Optimal Depth-Three Circuits for Inner Product · CCC 2026 |
Computational complexity
algebraic complexity |
0.3 | 1 | 2026 | Optimal Depth-Three Circuits for Inner Product · CCC 2026 |
Methods — techniques the papers use, named apart from their topics
computer search · 1.0automorphism group orbits · 1.0analytic combinatorics · 1.0
| Year | Publication | Venue | Position |
|---|---|---|---|
| 2026 | Optimal Depth-Three Circuits for Inner ProductabstractWe show that Inner Product in 2n variables, IP_n(x, y) = x₁y₁ ⊕ … ⊕ x_ny_n, can be computed by depth-3 bottom fan-in 2 circuits of size poly(n)⋅ (9/5)ⁿ, matching the lower bound of Göös, Guan, and Mosnoi (Inform. Comput.'24). Our construction is obtained via the following steps. 1) We provide a general template for constructing optimal depth-3 circuits with bottom fan-in k for an arbitrary function f. We do this in two steps. First, we partition f^{-1}(1) into orbits of its automorphism group. Second, for each orbit, we construct one k-CNF that (a) accepts the largest number of inputs from that orbit and (b) rejects all inputs rejected by f. 2) We instantiate the template for IP_n and k = 2. Guided by the intuition (which we call modularity principle) that optimal 2-CNFs can be constructed by taking the conjunction of variable-disjoint copies of smaller 2-CNFs, we use computer search to identify a small set of building block 2-CNFs over at most 4 variables. 3) We again use computer search to discover appropriate combinations (disjoint conjunctions) of building blocks to arrive at optimal 2-CNFs and analyze them using techniques from analytic combinatorics. We believe that the approach outlined in this paper can be applied to a wide range of functions to determine their depth-3 complexity. Mohit Gurumukhani, Daniel Kleber, Ramamohan Paturi, Christopher D. Rosin, Navid Talebanfard |
CCC | 2 |