90 reputation
6
bio website
location Cambridge, MA.
age
visits member for 3 years, 6 months
seen Apr 14 '13 at 4:44
Interested in Complexity theory.

Jul
2
awarded  Curious
Jan
24
revised Decomposition of projectors: A generalized format
edited tags; edited title
Jan
20
asked Decomposition of projectors: A generalized format
Dec
7
awarded  Commentator
Dec
6
comment Existence of (Cut-Based) pseudorandom graphs beating the random graph
Second comment: I don't see why your argument resolves the general case. I might be making a silly mistake but consider the following: Let $G$ be (a family) of counterexample to above,i.e. $|E(S,S^c)-|S||S^c|/2|\leq o(n^{3/2})$ .Then use your above construction to take $E(S,T)\geq 1/2 |S||T|+ \Omega(n^{3/2})$ .Let $U=(S\cup T)^c$. Apply the assumptions above to the cuts $(S, U\cup T)$ and $(T,S \cup U)$. This will imply that $E(S,U)≤\frac{|S||U|}{2}−\Omega(n^{3/2})$ and similarly for $(S,T)$. But this would imply a large deviation in the cut $(S\cup T,U)$. Doesn't it?
Dec
6
comment Existence of (Cut-Based) pseudorandom graphs beating the random graph
We wouldn't be done with the reduction yet because the "cut" that we get in $G$ might be in the form $(S,T)$ such that $S\cap T\neq \emptyset$. But I think in that case if $S\cap T$ is large enough to be annoying, you should be able to still get the desired result by taking the intersection $S\cap T$ and taking a random cut across it. You basically reduce to the case that if a graph has relative density bounded away from 1/2 the above result is easy by taking random cuts. I hope the hand-wavy argument above actually goes through
Dec
6
comment Existence of (Cut-Based) pseudorandom graphs beating the random graph
This is really interesting. I have two comments: First of all, Can't you deduce the general statement of your weak form a reduction: Let G=(V,E) be our graph and Take G1 and G2 to be two copies of G. Take G′=$G_1\cup G_2$ and now connect $v\in G_1$ with $u\in G_2$ if their preimage in G were not connected. Now the relative degree of each vertex would be 1/2 in G′. Now any cut ,or weak-cut, deviation in G′ will manifest itself with deviation in G losing a factor of 1/4 in the reduction.
Dec
5
comment Existence of (Cut-Based) pseudorandom graphs beating the random graph
The approach of taking a random partition and analyzing higher moments would probably not be sufficiently strong to prove this. But one approach could be to use the fact that we know this for random graphs, and hence for graphs $O(n^{3/2})$ close to random graphs. And given a graph G we have to see what this non-randomness can give us. Maybe in graphs far away from random one can use a random partition to achieve this. (indeed if the relative density is bounded away from 1/2 this works)Also some have suggested that maybe \emph{discrepancy theory} is the keyword in this problem.
Dec
5
revised Existence of (Cut-Based) pseudorandom graphs beating the random graph
added 1 characters in body; edited title
Dec
5
asked Existence of (Cut-Based) pseudorandom graphs beating the random graph
Dec
4
comment The minimum size of Max-Cut for graphs of half density
Thanks! I don't know how I didn't see that myself! But for the application that I had in mind what is really necessary is that a graph $G=(V,E)$ such that for any $S\subset V$ we have $|E(S,S^c)-\frac{|S||S^c|}{2}|\leq o(n^{3/2})$. Maybe I ask about the existence of such graphs in another question.
Dec
4
accepted The minimum size of Max-Cut for graphs of half density
Dec
3
revised The minimum size of Max-Cut for graphs of half density
edited title
Dec
3
revised The minimum size of Max-Cut for graphs of half density
added 2 characters in body; added 34 characters in body; added 127 characters in body
Dec
3
awarded  Editor
Dec
3
revised The minimum size of Max-Cut for graphs of half density
edited tags; edited title
Dec
3
asked The minimum size of Max-Cut for graphs of half density
Nov
16
comment A simple stopping time problem.
please do, Ori !
Nov
16
comment A simple stopping time problem.
yes I think that is not a $1$ ; rather it is a $\frac{1}{s+1}$ but beside that I don't any possible trivial calculation problem. do you ?
Nov
16
accepted A simple stopping time problem.