1) La descarga del recurso depende de la página de origen
2) Para poder descargar el recurso, es necesario ser usuario registrado en Universia

Opción 1: Descargar recurso

Detalles del recurso


We give a deterministic O˜(log n)-space algorithm for approximately solving linear systems given by Laplacians of undirected graphs, and consequently also approximating hitting times, commute times, and escape probabilities for undirected graphs. Previously, such systems were known to be solvable by randomized algorithms using O(log n) space (Doron, Le Gall, and Ta-Shma, 2017) and hence by deterministic algorithms using O(log3/2 n) space (Saks and Zhou, FOCS 1995 and JCSS 1999). Our algorithm combines ideas from time-efficient Laplacian solvers (Spielman and Teng, STOC ‘04; Peng and Spielman, STOC ‘14) with ideas used to show that UNDIRECTED S-T CONNECTIVITY is in deterministic logspace (Reingold, STOC ‘05 and JACM ‘08; Rozenman and Vadhan, RANDOM ‘05).

Pertenece a

Digital Access to Scholarship at Harvard  


Murtagh, Jack -  Reingold, Omer -  Sidford, Aaron -  Vadhan, Salil P. - 

Id.: 70835343

Idioma: inglés (Estados Unidos)  - 

Versión: 1.0

Estado: Final

Tipo de recurso: Conference Paper  - 

Tipo de Interactividad: Expositivo

Nivel de Interactividad: muy bajo

Audiencia: Estudiante  -  Profesor  -  Autor  - 

Estructura: Atomic

Coste: no

Copyright: sí

: open

Requerimientos técnicos:  Browser: Any - 

Relación: [References] doi:10.1109/FOCS.2017.79
[References] https://arxiv.org/abs/1708.04634
[References] 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS)

Fecha de contribución: 07-ene-2018


* Quick submit: 2017-09-17T15:42:00-0400
* Murtagh, Jack, Omer Reingold, Aaron Sidford, Salil Vadhan. 2017. Derandomization Beyond Connectivity: Undirected Laplacian Systems in Nearly Logarithmic Space. In Proceedings of the 58th Symposium on Foundations of Computer Science (FOCS 2017), Berkeley, CA, October 15-17, 2017.
* 0272-5428

Otros recursos del mismo autor(es)

  1. Faster Algorithms for Computing the Stationary Distribution, Simulating Random Walks, and More In this paper, we provide faster algorithms for computing variousfundamental quantities associated w...
  2. Almost-linear-time algorithms for Markov chains and new spectral primitives for directed graphs In this paper, we begin to address the longstanding algorithmic gap between general and reversible M...
  3. Socioeconomic Status and Reading Disability: Neuroanatomy and Plasticity in Response to Intervention Although reading disability (RD) and socioeconomic status (SES) are independently associated with va...
  4. Differentially Private Chi-Squared Hypothesis Testing: Goodness of Fit and Independence Testing Hypothesis testing is a useful statistical tool in determining whether a given model should be rejec...
  5. Differentially Private Release and Learning of Threshold Functions We prove new upper and lower bounds on the sample complexity of (ε, δ) differentially private algori...

Otros recursos de la mismacolección

  1. Trouvaille: A Conversation About the Proofs of Maurice Blanchot’s L’Entretien Infini at Houghton Library Libraries/Museums
  2. De L’ethnologie de L’échec au Collage des Arts Romance Languages and Literatures
  3. Which findings should be published? Given a scarcity of journal space, what is the socially optimal rule for determining whether an emp...
  4. A quick relaxation exercise for people with chronic obstructive pulmonary disease: explorative randomized controlled trial Background: People with Chronic Obstructive Pulmonary Disease (COPD) suffer from dyspnoea, which may...
  5. Embryonic and postnatal neurogenesis produce functionally distinct subclasses of dopaminergic neuron Most neurogenesis in the mammalian brain is completed embryonically, but in certain areas the produc...

Aviso de cookies: Usamos cookies propias y de terceros para mejorar nuestros servicios, para análisis estadístico y para mostrarle publicidad. Si continua navegando consideramos que acepta su uso en los términos establecidos en la Política de cookies.