Análise de complexidade de tempo para o algoritmo UST-CONN de Reingold

Qual é a complexidade temporal exata do algoritmo de espaço de log não-direcionado de st-connectivity de Omer Reingold?

cc.complexity-theory randomness Suresh Venkat
fonte

Por favor seja mais específico. Descreva sua pergunta com detalhes suficientes e cite as referências conforme apropriado.

MS Dousti

Eu acho que a pergunta é bastante inequívoca: doi.acm.org/10.1145/1391289.1391291 é o papel.

András Salamon

A pergunta é bastante clara para quem trabalha na área, mas provavelmente é uma boa ideia pedir aos pôsteres que forneçam mais informações para que um público mais amplo possa entender a pergunta.

Robin Kothari

Respostas:

Parece que a complexidade temporal do algoritmo de Reingold não é tratada no artigo de Reingold nem no livro de Arora-Barak. Parece também que a análise é bastante entediante, pois a complexidade do tempo depende do gráfico exato do expansor usado na construção e de algumas constantes que são escolhidas como "suficientemente grandes".

$G$ $G'$ $l = O(\log n)$ $O$ $G'$ $d = 2^b$ $b$ $d^l = O(n^c)$ $c$ $c \ge 10^9b$

Janne H. Korhonen
fonte

da próxima vez, não marque sua resposta como wiki da comunidade. Caso contrário, você não receberá crédito por sua resposta!

Ryan Williams

Eu estava pensando que alguém poderia refinar minha análise e não percebi que você não obtém reputação dos wikis da comunidade. Ah bem.

Janne H. Korhonen