Nonembeddability theorems via Fourier analysis

	This Article
	Subscribers, please Login Purchase article: $19 PDF IEEE Xplore Subscribers RSS feed
	Share
	Email this Article to a friend
	Bibliographic References
	ASCII Text BibTex RefWorks Procite/RefMan/Endnote
	Add to:
	Digg Furl Spurl Blink Simpy Google Del.icio.us Y!MyWeb
	Search
	Similar Articles Articles by Subhash Khot Articles by Assaf Naor

46th Annual IEEE Symposium on Foundations of Computer Science (FOCS'05)

Pittsburgh, Pennsylvania, USA

October 23-October 25

ISBN: 0-7695-2468-0

	ASCII Text	x
	Subhash Khot, Assaf Naor, "Nonembeddability theorems via Fourier analysis," Foundations of Computer Science, Annual IEEE Symposium on, pp. 101-112, 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS'05), 2005.

	BibTex	x
	@article{ 10.1109/SFCS.2005.54, author = {Subhash Khot and Assaf Naor}, title = {Nonembeddability theorems via Fourier analysis}, journal ={Foundations of Computer Science, Annual IEEE Symposium on}, volume = {0}, year = {2005}, isbn = {0-7695-2468-0}, pages = {101-112}, doi = {http://doi.ieeecomputersociety.org/10.1109/SFCS.2005.54}, publisher = {IEEE Computer Society}, address = {Los Alamitos, CA, USA}, }

	RefWorks Procite/RefMan/Endnote	x
	TY - CONF JO - Foundations of Computer Science, Annual IEEE Symposium on TI - Nonembeddability theorems via Fourier analysis SN - 0-7695-2468-0 SP101 EP112 A1 - Subhash Khot, A1 - Assaf Naor, PY - 2005 KW - null VL - 0 JA - Foundations of Computer Science, Annual IEEE Symposium on ER -

Subhash Khot, Georgia Institute of Technology

Assaf Naor, Microsoft Corporation Theory Group, Microsoft Research

DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/SFCS.2005.54

Various new nonembeddability results (mainly into L1) are proved via Fourier analysis. In particular, it is shown that the Edit Distance on {0,1}^d has L1 distortion (\log d)^frac{1}{2}^{} - (1). We also give new lower bounds on the L1 distortion of quotients of the discrete hypercube under group actions, and the transportation cost (Earthmover) metric.

Citation:

Subhash Khot, Assaf Naor, "Nonembeddability theorems via Fourier analysis," focs, pp.101-112, 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS'05), 2005

Peer Review Notice | Give Us Feedback

Usage of this product signifies your acceptance of the Terms of Use.