Demo Data from VLDB 2026 / reviewers in the wild / expert
Pratyush Vempati
dblp:438/9017
· DBLP profile ↗
1ranked-venue papers
0as first author
1since 2021 · last 2026
0009-0006-6645-0743ORCID · reported
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
algebraic complexity |
1.0 | 1 | 2026 | Multilinear Formula Lower Bounds for Sparse Determinants · CCC 2026 |
Computational complexity › algebraic complexity
arithmetic formulas |
1.0 | 1 | 2026 | Multilinear Formula Lower Bounds for Sparse Determinants · CCC 2026 |
Computational complexity › circuit complexity › formula size
formula size lower bound |
1.0 | 1 | 2026 | Multilinear Formula Lower Bounds for Sparse Determinants · CCC 2026 |
Computational complexity › algebraic complexity › arithmetic formulas
multilinear formulas |
1.0 | 1 | 2026 | Multilinear Formula Lower Bounds for Sparse Determinants · CCC 2026 |
Methods — techniques the papers use, named apart from their topics
random graph theory · 1.0partial derivatives method · 1.0concentration inequalities · 1.0
| Year | Publication | Venue | Position |
|---|---|---|---|
| 2026 | Multilinear Formula Lower Bounds for Sparse DeterminantsabstractRaz (2009) proved that multilinear formulas computing the determinant of a generic n × n matrix require size n^{Ω(log n)}. A fundamental question in understanding this lower bound is identifying which structural properties of the determinant drive this hardness. Is it the quadratic number of variables? The dense connectivity? Specific algebraic symmetries? We establish that density is not essential. We prove the existence of n × n symbolic matrices with only Θ(nlog⁶ n) nonzero entries - reducing the variable count by a factor of n/log⁶ n - such that any multilinear formula computing their determinants still requires size n^{Ω(log n)}. Our construction uses rectangle sampling from the complete bipartite graph to generate sparse matrices that simultaneously maintain perfect matchings (ensuring nonzero determinant) while exhibiting diagonal imbalance under random vertex permutations - a geometric property we identify as the key driver of factor imbalance in Raz’s framework. This demonstrates that Raz’s partial derivatives method is remarkably robust to sparsification, and suggests that the fundamental source of multilinear hardness for determinant lies in expansion-like combinatorial structure rather than density. Our techniques combine concentration inequalities for dependent random variables with insights from random graph theory. Pruthvi Boyapati, Suryajith Chillara, Pratyush Vempati |
CCC | 3 |