Finite Groups and Complexity Theory: From Leningrad to Saint Petersburg via Las Vegas (Q3007625)

scientific article

Language	Label	Description	Also known as
English	Finite Groups and Complexity Theory: From Leningrad to Saint Petersburg via Las Vegas	scientific article

Statements

instance of

scholarly article

0 references

title

Finite Groups and Complexity Theory: From Leningrad to Saint Petersburg via Las Vegas (English)

0 references

author

László Babai

0 references

published in

Computer Science – Theory and Applications

0 references

publication date

17 June 2011

0 references

zbMATH Keywords

matrix group membership problem

0 references

describes a project that uses

GAP

0 references

MaRDI profile type

MaRDI publication profile

0 references

full work available at URL

https://doi.org/10.1007/978-3-642-20712-9_13

0 references

cites work

Q3002783

0 references

A fast and simple randomized parallel algorithm for the maximal independent set problem

0 references

Q2759616

0 references

Proof verification and the hardness of approximation problems

0 references

Isomorphism problem for a class of point-symmetric structures

0 references

Random oracles separate PSPACE from the polynomial-time hierarchy

0 references

Bounded Round Interactive Proofs in Finite Groups

0 references

Evasiveness and the Distribution of Prime Numbers

0 references

Q4240509

0 references

Polynomial-time theory of matrix groups

0 references

Fast Monte Carlo algorithms for permutation groups

0 references

Q4237394

0 references

Non-deterministic exponential time has two-prover interactive protocols

0 references

Short presentations for finite groups

0 references

Black-box recognition of finite simple groups of Lie type by statistics of element orders

0 references

Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes

0 references

Q3579473

0 references

On the Number of<i>p</i>-Regular Elements in Finite Simple Groups

0 references

Q2759618

0 references

Local Expansion of Symmetrical Graphs

0 references

Bounded-width polynomial-size branching programs recognize exactly those languages in $NC^ 1$

0 references

Q4335290

0 references

Relative to a Random Oracle<i>A</i>, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1

0 references

Self-testing/correcting with applications to numerical problems

0 references

Uniform expansion bounds for Cayley graphs of $\text{SL}_2(\mathbb F_p)$.

0 references

An improved method for generating the centralizer of an involution

0 references

Approximate subgroups of linear groups.

0 references

Q2759621

0 references

Generating random elements of a finite group

0 references

An optimal lower bound on the number of variables for graph identification

0 references

Constructive recognition of 𝑃𝑆𝐿(2,𝑞)

0 references

Q3684278

0 references

Generating random elements in finite groups.

0 references

Q3912839

0 references

Expansion of product replacement graphs

0 references

Q3002823

0 references

The knowledge complexity of interactive proof-systems

0 references

Quasirandom Groups

0 references

Growth and generation in $\text{SL}_2(\mathbb{Z}/p\mathbb{Z})$.

0 references

Constructive membership in black-box groups

0 references

Q3929039

0 references

Short presentations for three-dimensional unitary groups.

0 references

Random generation of combinatorial structures from a uniform distribution

0 references

A topological approach to evasiveness

0 references

Sylow's theorem in polynomial time

0 references

Black box classical groups

0 references

Efficient representation of perm groups

0 references

Ramanujan graphs

0 references

Isomorphism of graphs of bounded valence can be tested in polynomial time

0 references

Computing the composition factors of a permutation group in polynomial time

0 references

Q4230332

0 references

Q4273608

0 references

Explicit constructions of graphs without short cycles and low density codes

0 references

Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators

0 references

A note on the graph isomorphism counting problem

0 references

Approximate inclusion-exclusion

0 references

Pseudorandom generators for space-bounded computation

0 references

Growth in finite simple groups of Lie type

0 references

Undirected connectivity in log-space

0 references

Entropy waves, the zig-zag graph product, and new constant-degree expanders

0 references

Q4787523

0 references

Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer

0 references

Q3895641

0 references

On a class of doubly transitive groups

0 references

On an isoperimetric inequality for infinite finitely generated groups

0 references

Identifiers

zbMATH Open document ID

1332.68003

0 references

DOI

10.1007/978-3-642-20712-9_13

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

0 references

0 references

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:3007625