Finite Groups and Complexity Theory: From Leningrad to Saint Petersburg via Las Vegas
From MaRDI portal
Publication:3007625
DOI10.1007/978-3-642-20712-9_13zbMath1332.68003OpenAlexW39512316MaRDI QIDQ3007625
Publication date: 17 June 2011
Published in: Computer Science – Theory and Applications (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-20712-9_13
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) History of computer science (68-03) Probabilistic methods in group theory (20P05) History of group theory (20-03) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)
Uses Software
Cites Work
- Computing the composition factors of a permutation group in polynomial time
- Non-deterministic exponential time has two-prover interactive protocols
- Approximate subgroups of linear groups.
- Expansion of product replacement graphs
- Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators
- Generating random elements in finite groups.
- Sylow's theorem in polynomial time
- A topological approach to evasiveness
- Random generation of combinatorial structures from a uniform distribution
- Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
- Random oracles separate PSPACE from the polynomial-time hierarchy
- Ramanujan graphs
- Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
- Explicit constructions of graphs without short cycles and low density codes
- Isomorphism of graphs of bounded valence can be tested in polynomial time
- Approximate inclusion-exclusion
- Efficient representation of perm groups
- Pseudorandom generators for space-bounded computation
- An optimal lower bound on the number of variables for graph identification
- A note on the graph isomorphism counting problem
- Self-testing/correcting with applications to numerical problems
- Short presentations for finite groups
- An improved method for generating the centralizer of an involution
- On an isoperimetric inequality for infinite finitely generated groups
- Entropy waves, the zig-zag graph product, and new constant-degree expanders
- Fast Monte Carlo algorithms for permutation groups
- Growth and generation in \(\text{SL}_2(\mathbb{Z}/p\mathbb{Z})\).
- Uniform expansion bounds for Cayley graphs of \(\text{SL}_2(\mathbb F_p)\).
- Black box classical groups
- On the Number ofp-Regular Elements in Finite Simple Groups
- Evasiveness and the Distribution of Prime Numbers
- Proof verification and the hardness of approximation problems
- Growth in finite simple groups of Lie type
- Constructive membership in black-box groups
- Quasirandom Groups
- Undirected connectivity in log-space
- A fast and simple randomized parallel algorithm for the maximal independent set problem
- Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
- Bounded Round Interactive Proofs in Finite Groups
- Isomorphism problem for a class of point-symmetric structures
- Local Expansion of Symmetrical Graphs
- The knowledge complexity of interactive proof-systems
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- Black-box recognition of finite simple groups of Lie type by statistics of element orders
- Generating random elements of a finite group
- Polynomial-time theory of matrix groups
- Constructive recognition of 𝑃𝑆𝐿(2,𝑞)
- On a class of doubly transitive groups
- Short presentations for three-dimensional unitary groups.
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
