Entropy waves, the zig-zag graph product, and new constant-degree expanders and extractors

By Omer Reingold, Salil P. Vadhan, Avi Wigderson. Proceedings 41st Annual Symposium on Foundations of Computer Science, 2000

444 citations recorded by the source corpus.

Subfields: Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/9cba141b6f6aa32c88de6c82832c274a5bcc3e33

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Statistical and Nonlinear Physics

Citations in the corpus

Efficient Distributed Online Prediction and Stochastic Optimization With Approximate Distributed Averaging (2014, unknown): “…using all of the data, which can be very time-consuming when N is large, a stochastic gradient is obtained by drawing one sample x ( t ) = x i independently and uniformly from the collection at each iteration, and using ∇ w f ( w ( t ) , x ( t )) as a surrogate for 1 N =1 ∇ w f ( w ( t ) , x i ) .”
Opinion dynamics in social networks with stubborn agents: Equilibrium and convergence rate (2014, background): “A fully stubborn agent i with Ki = ∞ corresponds to an ideal voltage source with zero internal resistance.”
Cutoff phenomena for random walks on random regular graphs (2008, methodology): “ar expander with 3 kd 1 would do (and in case k<d 1, the graph should then be completed arbitrarily to be d-regular). See, e.g., [1] for an explicit construction of a 3-regular graph, as well as [24] and the references therein for additional explicit constructions of constant-degree expander grap”
Communication/Computation Tradeoffs in Consensus-Based Distributed Optimization (2012, methodology): “Below we focus on two particular cases and take G to be either a complete graph (i.e., all pairs of nodes communicate) or a k -regular expander [1].”
Recent Developments in Explicit Constructions of Extractors (2002, background): “Using this approach loses gives an entropy loss of D. The main contribution of [ RVW00 ] is a way to perform this argument without suering this loss.”
Correlation clustering in general weighted graphs (2006, methodology): “To construct our example G, set the weight of every edge in G′ to 1 and its label to 〈+〉.”
Gossip Algorithms (2009, unknown): “) → T ave ( ǫ ) = Ω ( n 2 log ǫ”