Demonstration venue · read-only. Every page can be browsed; the buttons that would change it are switched off. Create an account to run TaxoReview on your own data.

Aner Shalev

dblp:05/4376 · DBLP profile ↗
← Back
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

TopicWeightPapersLastEvidence papers
Combinatorics and discrete mathematics
group theory
0.122005
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.112005
The hidden subgroup problem and permutation group theory · SODA 2005
Quantum computing and quantum information
quantum algorithms
0.112005
The hidden subgroup problem and permutation group theory · SODA 2005
Graph algorithms and graph theory
expander graphs
0.012004
A new family of Cayley expanders (?) · STOC 2004
Automata and formal languages
wreath products
0.012004
A new family of Cayley expanders (?) · STOC 2004
Coding theory › error-correcting codes › code construction
explicit constructions
0.012004
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
YearPublicationVenuePosition
2005 The hidden subgroup problem and permutation group theory
Julia Kempe, Aner Shalev
SODA2
2004 A new family of Cayley expanders (?)
abstract
We 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
STOC2