theory salon

« first day (765 days earlier) ← previous day next day → last day (2864 days later) »

3:05 AM

Sanjeev Arora on rethinking the graduate algorithms course / Windows on Theory

> Programming assignments need to be brought back! CS students like hands-on learning: an algorithm becomes real only once they see it run on real data. Also, computer scientists today —whether in industry or academia—rely on subroutine libraries and scripting languages.
> A few lines in Matlab and Scipy can be written in minutes and run on datasets of millions or billions of numbers. No JAVA or C++ needed! Algorithms education should weave in such powerful tools. It is beneficial even for theory students play with them.

11 hours later…

Jim

1:38 PM

5 hours later…

Jim

6:34 PM

@ThomasKlimpel , In abstract of paper sciencedirect.com/science/article/pii/S0021869314004967 , L. Babai said-

"
We conjecture that the order of the automorphism group of a non-trivial, non-graphic SR graph is quasi-polynomially bounded, i.e., it is at most $exp((log⁡n)^C))$ for some constant $C$, where n is the number of vertices.

While the conjecture remains open, we find surprisingly strong bounds on important parameters of the automorphism group. In particular, we show that the order of every automorphism is $O(n^8)$, and in fact $O(n)$ if we exclude the line-graphs of certain geometries. "

would u please interpret "we show that the order of every automorphism is $O(n^8)$" . If a permutation matrix P of AUT (G), then P*G*(1/P) = G, how Can I interpret previous line in terms of P. I could not read the paper . though it is pointed to T\K anyone can answer .

P has order $O(n^8)$?

also 1. size of automorphism set= order of automorphism group = number of distinct automorphism = number of distinct permutation P of AUT(G) ?

2. could not grasp "order of every automorphism " , read math.stackexchange.com/questions/189546/… , no help.

3. every automorphism create a group of order $O(n^8)$?

1 hour later…

vzn

8:31 PM

Q: What evidence is there that Graph Isomorphism is not in $P$?

Motivated by Fortnow's comment on my post, Evidence that Graph Isomorphism problem is not $NP$-complete, and by the fact that $GI$ is a prime candidate for $NP$-intermediate problem (not $NP$-complete nor in $P$), I am interested in known evidences that $GI$ is not in $P$. One such evidence is t...