EDBT 2026 Demo / reviewers in the wild / expert
Aner Shalev
dblp:05/4376
· DBLP profile ↗
2ranked-venue papers
0as first author
0since 2021 · last 2005
—ORCID · unresolved
Domains — the database's venue-derived domains; a paper can count in several
Theory of computation · 2
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 |
Quantum computing and quantum information · 34% Combinatorics and discrete mathematics · 32% Graph algorithms and graph theory · 15% |
Topics — the 6 heaviest of 6, each with the papers that count most for it
| Topic | Weight | Papers | Last | Evidence papers |
|---|---|---|---|---|
Combinatorics and discrete mathematics
group theory |
0.1 | 2 | 2005 | The hidden subgroup problem and permutation group theory · SODA 2005 A new family of Cayley expanders (?) · STOC 2004 |
Quantum computing and quantum information › quantum algorithms
hidden subgroup problem |
0.1 | 1 | 2005 | The hidden subgroup problem and permutation group theory · SODA 2005 |
Quantum computing and quantum information
quantum algorithms |
0.1 | 1 | 2005 | The hidden subgroup problem and permutation group theory · SODA 2005 |
Graph algorithms and graph theory
expander graphs |
0.0 | 1 | 2004 | A new family of Cayley expanders (?) · STOC 2004 |
Automata and formal languages
wreath products |
0.0 | 1 | 2004 | A new family of Cayley expanders (?) · STOC 2004 |
Coding theory › error-correcting codes › code construction
explicit constructions |
0.0 | 1 | 2004 | A new family of Cayley expanders (?) · STOC 2004 |
Methods — techniques the papers use, named apart from their topics
zig-zag product · 0.0commutator width · 0.0
| Year | Publication | Venue | Position |
|---|---|---|---|
| 2005 | The hidden subgroup problem and permutation group theory
Julia Kempe, Aner Shalev |
SODA | 2 |
| 2004 | A new family of Cayley expanders (?)abstractWe assume that for some fixed large enough integer d, the symmetric group Sd can be generated as an expander using d1/30 generators. Under this assumption, we explicitly construct an infinite family of groups Gn, and explicit sets of generators Yn ⊂ Gn, such that all generating sets have bounded size (at most d1/7), and the associated Cayley graphs are all expanders. The groups Gn above are very simple, and completely different from previous known examples of expanding groups. Indeed, Gn is (essentially) all symmetries of the d-regular tree of depth n. The proof is completely elementary, using only simple combinatorics and linear algebra. The recursive structure of the groups Gn (iterated wreath products of the alternating group Ad) allows for an inductive proof of expansion, using the group theoretic analogue [4] of the zig-zag graph product of [38]. The explicit construction of the generating sets Yn uses an efficient algorithm for solving certain equations over these groups, which relies on the work of [33] on the commutator width of perfect groups.We stress that our assumption above on weak expansion in the symmetric group is an open problem. We conjecture that it holds for all d. We discuss known results related to its likelihood in the paper. Eyal Rozenman, Aner Shalev, Avi Wigderson |
STOC | 2 |