« first day (4 days earlier)      last day (175 days later) » 

vzn
vzn
12:18 AM
sorry my bad! correction! iso peri metric
geez just realized you spell it differently in different papers
 
vzn
vzn
12:35 AM
it would be helpful if you could cite something online about ISP. is it a major problem in extremal set theory? havent seen it yet via google.
this seems to be a pretty good survey:
does anything in there look close?
is it roughly a discrete version of the isoperimetric problem?
Isoperimetric inequality
In mathematics, the isoperimetric inequality is a geometric inequality involving the square of the circumference of a closed curve in the plane and the area of a plane region it encloses, as well as its various generalizations. ' literally means "having the same perimeter". Specifically, the isoperimetric inequality states, for the length L of a closed curve and the area A of the planar region that it encloses, that :4\pi A \le L^2, and that equality holds if and only if the curve is a circle. The isoperimetric problem is to determine a plane figure of the largest possible area whose bou...
 
vzn
vzn
12:52 AM
heres another paper that classifies types of discrete isoperimetric inequalities. anything related?
this question seems to indicate in an offhand comment that information theory can be used to prove "isoperimetric inequalities on the boolean cube" but dont see much further.
43
Q: Information Theory used to prove neat combinatorial statements?

Dana MoshkovitzWhat's your favorite examples where information theory is used to prove a neat combinatorial statement in a simple way ? Some examples I can think of are related to lower bounds for locally decodable codes, e.g., in this paper: suppose that for a bunch of binary strings $x_1,...,x_m$ of length $...

co.combinatorics big-list it.information-theory
 
 
2 hours later…
vzn
vzn
3:13 AM
the chung reference relates it to graphs via edge and vertex boundaries. sounding a little closer to TCS.
section 12 relates isoperimetric inequalities to chromatic numbers of graphs. graph coloring of course is often highly related to NP complete problems, but it doesnt show a direct connection.
ok one of your online paper titles wasnt exactly the same as the title in the reference [5] but now see obviously which one it is.
 
vzn
vzn
3:43 AM
looking at the (earliest) hamming distance paper. see now you cite alon & boppana, razborov, papadimitriou at the very end, the final short sketchy paragraph... the punchline! aha. this reminds me a little of wiles famous 3 lectures hah. =)
you do mention P/NP at the very end.
 
 
2 hours later…
Jun
Jun
5:51 AM
I think the isometric problem was said open in the handbook of combinatorics around 2006. the problem states:
let U =fam of m-sets, d=integer be given. \sigma(U,d) = {m-sets t ; \exists s\in U, }
\sigma(U, d)={m-set t; \exists s \in U, |t - s| \le d}
\sigma(U, d): ball (cover) of U of radius d.
Given two integers d and |U|=size, what is
min_{all U such that |U|=size} |\sigma(U,d)| ?
i remember the problem is open even if d is constant
 
 
12 hours later…
vzn
vzn
5:47 PM
ok so am starting to get a little bit better picture. you conjectured early on that DISP relates to P vs NP via monotone circuits even though there seems to be nearly zero connection in the literature... [need to look up that ref...]
did you hear about DISP from noga alon? how did you 1st hear about DISP?
 
vzn
vzn
6:03 PM
agree that DISP seems to relate to cliques & monotone circuits (via some of my own research) but dont think it has been related in any published papers...? does the frankl ref say anything about TCS, P/NP, circuits, cliques, graphs, etc?
you refer to the hamming ball or sphere. [equivalent right?]
is it related to the hamming sphere packing bound?
Hamming bound
In mathematics and computer science, in the field of coding theory, the Hamming bound is a limit on the parameters of an arbitrary block code: it is also known as the sphere-packing bound or the volume bound from an interpretation in terms of packing balls in the Hamming metric into the space of all possible words. It gives an important limitation on the efficiency with which any error-correcting code can utilize the space in which its code words are embedded. A code which attains the Hamming bound is said to be a perfect code. Background on error-correcting codes An original message an...
bezrukov sec 2.b mentions "shifting techniques". any relation?
 
 
4 hours later…
vzn
vzn
9:48 PM
bezrukov sec 7.e, 3 example applications of DISP in TCS. unreliable networks in parallel computers, scheduling.
 
 
1 hour later…
vzn
vzn
11:16 PM
this ref [5] frankl/furedi from your hamming distance paper is online.
 

« first day (4 days earlier)      last day (175 days later) »