NDLI: Vertex cuts, random walks, and dimension reduction in series-parallel graphs

Please wait, while we are loading the content...

Statistically-hiding commitment from any one-way function

Voronoi diagrams in n · 2o(√lg lg n) time

Faster integer multiplication

Smooth sensitivity and sampling in private data analysis

How to rank with few errors

On the submodularity of influence in social networks

Hardness of routing with congestion in directed graphs

Iteratively constructing preconditioners via the conjugate gradient method

Distributed computing theory: algorithms, impossibility results, models, and proofs

The condition number of a randomly perturbed matrix

Circuit lower bounds for Merlin-Arthur classes

Tight integrality gaps for Lovasz-Schrijver LP relaxations of vertex cover and max cut

Linear probing with constant independence

Limitations of VCG-based mechanisms

Interval completion with few edges

Parallel repetition: simplifications and the no-signaling case

Randomly coloring planar graphs with fewer colors than the maximum degree

Property testing in hypergraphs and the removal lemma

Exponential separations for one-way quantum communication complexity, with applications to cryptography

Playing games with approximation algorithms

Toward a general theory of quantum games

All-pairs bottleneck paths for general graphs in truly sub-cubic time

Uncertainty principles, extractors, and explicit embeddings of l2 into l1

Survivable network design with degree or order constraints

Lower bounds for randomized read/write stream algorithms

On achieving the "best of both worlds" in secure multiparty computation

Lower bounds for 2-dimensional range counting

Fourier meets möbius: fast subset convolution

The price of privacy and the limits of LP decoding

Approximation algorithms for budgeted learning problems

First to market is not everything: an analysis of preferential attachment with fitness

Polynomial flow-cut gaps and hardness of directed cut problems

On the convergence of Newton's method for monotone systems of polynomial equations

Balanced allocations: the weighted case

Interpolation of depth-3 arithmetic circuits with two multiplication gates

Rank complexity gap for Lovász-Schrijver and Sherali-Adams proof systems

Optimal suffix selection

The communication complexity of uncoupled nash equilibrium procedures

Computing crossing number in linear time

An efficient parallel repetition theorem for Arthur-Merlin games

Inapproximability of the Tutte polynomial

Testing k-wise and almost k-wise independence

Negative weights make adversaries stronger

Reordering buffers for general metric spaces

Search via quantum walk

More algorithms for all-pairs shortest paths in weighted graphs

Vertex cuts, random walks, and dimension reduction in series-parallel graphs

Approximating minimum bounded degree spanning trees to within one of optimal

Lower bounds in communication complexity based on factorization norms

Zero-knowledge from secure multiparty computation

Combinatorial complexity in O-minimal geometry

An approximation algorithm for max-min fair allocation of indivisible goods

Stability of the max-weight routing and scheduling protocol in dynamic networks and at critical loads

Balanced max 2-sat might not be the hardest

A combinatorial, primal-dual approach to semidefinite programs

Towards 3-query locally decodable codes of subexponential length

Separating $AC^{0}$ from depth-2 majority circuits

Proportional response dynamics leads to market equilibrium

Terminal backup, 3D matching, and covering cubic graphs

Low-end uniform hardness vs. randomness tradeoffs for AM

Tensor-based hardness of the shortest vector problem to within almost polynomial factors

Low-degree tests at large distances

On the impossibility of a quantum sieve algorithm for graph isomorphism

Some new results on node-capacitated packing of A-paths

Local embeddings of metric spaces

Improved approximation for directed cut problems

Constructing non-computable Julia sets

Simple deterministic approximation algorithms for counting matchings

Tight bounds for asynchronous randomized consensus

A 3-query PCP over integers

One sketch for all: fast algorithms for compressed sensing

Eisenberg-Gale markets: algorithms and structural properties

Holographic algorithms: from art to science

Verifying and decoding in constant depth

Lattices that admit logarithmic worst-case to average-case connection factors

An Õ(mn) Gomory-Hu tree construction algorithm for unweighted graphs

Sampling-based dimension reduction for subspace approximation

Degree-constrained network flows

Vertex cuts, random walks, and dimension reduction in series-parallel graphs

Content Provider	ACM Digital Library
Author	Karagiozova, Adriana Brinkman, Bo Lee, James R.
Abstract	We consider questions about vertex cuts in graphs, random walks in metric spaces, and dimension reduction in $L_{1}$ and $L_{2};$ these topics are intimately connected because they can each be reduced to the existence ofvarious families of real-valued Lipschitz maps on certain metric spaces. We view these issues through the lens of shortest-path metricson series-parallel graphs, and we discussthe implications for a variety of well-known open problems. Our main results follow. Every n-point series-parallel metric embeds into $l_{1}^{dom}$ with O(√ log n) distortion, matchinga lower bound of Newman and Rabinovich. Our embeddings yield an O(√log n) approximation algorithm for vertex sparsestcut in such graphs, as well as an O(√log k) approximate max-flow/min-vertex-cut theorem for series-parallel instances withk terminals, improving over the O(log n) and O(log k) boundsfor general graphs. Every n-point series-parallel metric embeds withdistortion D into $l_{1}^{d}$ with d = $n^{1/Ω(D^{2})},matching$ the dimension reduction lower bound of Brinkman andCharikar. There exists a constant C > 0 such that if (X,d) is aseries-parallel metric then for every stationary, reversible Markovchain $Z_{t}_{t=0}^{∞}$ on X, we have for all t ≥ 0, $E[d(Z_{t},Z_{0})^{2}]$ ≤ Ct ·, $E[d(Z_{0},Z_{1})^{2}].$ More generally, we show thatseries-parallel metrics have Markov type 2. This generalizesa result of Naor, Peres, Schramm, and Sheffield for trees.
Starting Page	621
Ending Page	630
Page Count	10
File Format	PDF
ISBN	9781595936318
DOI	10.1145/1250790.1250882
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2007-06-11
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Dimension reduction Approximation algorithms Metric embeddings
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in