Search results for "Expander graphs"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
3	Denis Xavier Charles, Kristin E. Lauter, Eyal Z. Goren	Cryptographic Hash Functions from Expander Graphs.	J. Cryptology	2009	DBLP DOI BibTeX RDF	Supersingular elliptic curves, Elliptic curve cryptography, Expander graphs, Cryptographic hash functions, Ramanujan graphs, Isogenies
3	Harold N. Gabow	Using expander graphs to find vertex connectivity.	J. ACM	2006	DBLP DOI BibTeX RDF	graphs, Expander graphs, vertex connectivity
3	Debdeep Mukhopadhyay, Dipanwita Roy Chowdhury	Generation of Expander Graphs Using Cellular Automata and Its Applications to Cryptography.	ACRI	2006	DBLP DOI BibTeX RDF	Security, Efficiency, Cellular Automata, Expander Graphs, One-way functions
3	Yonatan Bilu, Nathan Linial	Constructing Expander Graphs by 2-Lifts and Discrepancy vs. Spectral Gap.	FOCS	2004	DBLP DOI BibTeX RDF	Lifts of Graphs, Signed Graphs, Expander Graphs, Discrepancy, Lifts
2	Joshua D. Batson, Daniel A. Spielman, Nikhil Srivastava	Twice-ramanujan sparsifiers.	STOC	2009	DBLP DOI BibTeX RDF	expander graphs, spectral graph theory
2	Venkatesan Guruswami, Christopher Umans, Salil P. Vadhan	Unbalanced expanders and randomness extractors from Parvaresh--Vardy codes.	J. ACM	2009	DBLP DOI BibTeX RDF	error-correcting codes, Expander graphs, condensers, list decoding, randomness extractors
2	Tom Høholdt, Heeralal Janwa	Optimal Bipartite Ramanujan Graphs from Balanced Incomplete Block Designs: Their Characterizations and Applications to Expander/LDPC Codes.	AAECC	2009	DBLP DOI BibTeX RDF	eigenvalues of graphs, finite geometries, LDPC and expander codes, Bipartite graphs, expander graphs, Ramanujan graphs, BIBD
2	Tom Høholdt	Codes from Expander Graphs.	ICMCTA	2008	DBLP DOI BibTeX RDF
2	Sumit Ganguly	Data Stream Algorithms via Expander Graphs.	ISAAC	2008	DBLP DOI BibTeX RDF
2	Avraham Ben-Aroya, Amnon Ta-Shma	A combinatorial construction of almost-ramanujan graphs using the zig-zag product.	STOC	2008	DBLP DOI BibTeX RDF	zig-zag product, expander graphs
2	Juan A. Garay, Rafail Ostrovsky	Almost-Everywhere Secure Computation.	EUROCRYPT	2008	DBLP DOI BibTeX RDF	secure message transmission, almost-everywhere agreement, bounded-degree networks, Secure multi-party computation, expander graphs
2	Venkatesan Guruswami, Christopher Umans, Salil P. Vadhan	Unbalanced Expanders and Randomness Extractors from Parvaresh-Vardy Codes.	IEEE Conference on Computational Complexity	2007	DBLP DOI BibTeX RDF	error-correcting codes, expander graphs, condensers, list decoding, randomness extractors
2	Peter Mahlmann, Christian Schindelhauer	Distributed random digraph transformations for peer-to-peer networks.	SPAA	2006	DBLP DOI BibTeX RDF	distributed algorithms, peer-to-peer networks, random graphs, expander graphs
2	Venkatesan Guruswami	Guest column: error-correcting codes and expander graphs.	SIGACT News	2004	DBLP DOI BibTeX RDF
2	Heeralal Janwa	Good Expander Graphs and Expander Codes: Parameters and Decoding.	AAECC	2003	DBLP DOI BibTeX RDF
2	Dawn Xiaodong Song, J. D. Tygar, David Zuckerman	Expander Graphs for Digital Stream Authentication and Robust Overlay Networks. (PDF / PS)	IEEE Symposium on Security and Privacy	2002	DBLP DOI BibTeX RDF
2	Harold N. Gabow	Using Expander Graphs to Find Vertex Connectivity.	FOCS	2000	DBLP DOI BibTeX RDF	nesting properties, separation triples, computational complexity, complexity, graph theory, expander graphs, undirected graph, digraph, time bound, vertex connectivity
2	Alan M. Frieze	Disjoint Paths in Expander Graphs via Random Walks: A Short Survey.	RANDOM	1998	DBLP DOI BibTeX RDF
2	Jon M. Kleinberg, Ronitt Rubinfeld	Short Paths in Expander Graphs.	FOCS	1996	DBLP DOI BibTeX RDF	inter-connection networks, disjoint paths problem, graph minor containment, polylogarithmic approximation, routing algorithms, greedy algorithm, network routing, multicommodity flow, expander graphs
2	David Gillman	A Chernoff bound for random walks on expander graphs	FOCS	1993	DBLP DOI BibTeX RDF	Ising system, finite random walk, entropy, random walks, expander graphs, weighted graph, error probability, partition function, Chernoff bound
1	Rieuwert J. Blok, Corneliu G. Hoffman, Alina Vdovina	Expander graphs from Curtis-Tits groups.	J. Comb. Theory, Ser. A	2012	DBLP DOI BibTeX RDF
1	Michelle Kendall, Keith Martin	On the Role of Expander Graphs in Key Predistribution Schemes for Wireless Sensor Networks.	IACR Cryptology ePrint Archive	2011	DBLP BibTeX RDF
1	Mohammad Hamed Firooz, Sumit Roy	Link Delay Estimation via Expander Graphs	CoRR	2011	DBLP BibTeX RDF
1	Oded Goldreich	Candidate One-Way Functions Based on Expander Graphs.	Studies in Complexity and Cryptography	2011	DBLP DOI BibTeX RDF
1	Oded Goldreich	Basic Facts about Expander Graphs.	Studies in Complexity and Cryptography	2011	DBLP DOI BibTeX RDF
1	Ho Yee Cheung, Lap Chi Lau, Kai Man Leung	Graph Connectivities, Network Coding, and Expander Graphs.	FOCS	2011	DBLP DOI BibTeX RDF
1	S.-J. Cho, U.-S. Choi, H.-D. Kim, Y.-H. Hwang, J.-G. Kim	60/102 Null Boundary Cellular Automata based expander graphs.	Automata	2010	DBLP BibTeX RDF
1	Chryssis Georgiou, Seth Gilbert, Dariusz R. Kowalski	Meeting the deadline: on the complexity of fault-tolerant continuous gossip.	PODC	2010	DBLP DOI BibTeX RDF	crashes and restarts, dynamic rumor injection, gossip, expander graphs
1	Arun S. Maiya, Tanya Y. Berger-Wolf	Sampling community structure.	WWW	2010	DBLP DOI BibTeX RDF	clustering, social networks, graphs, sampling, complex networks, community detection
1	Sonny Ben-Shimon, Michael Krivelevich	Vertex percolation on expander graphs.	Eur. J. Comb.	2009	DBLP DOI BibTeX RDF
1	Sina Jafarpour, Weiyu Xu, Babak Hassibi, A. Robert Calderbank	Efficient and robust compressed sensing using optimized expander graphs.	IEEE Transactions on Information Theory	2009	DBLP DOI BibTeX RDF
1	Tal Moran, Ronen Shaltiel, Amnon Ta-Shma	Non-interactive Timestamping in the Bounded-Storage Model.	J. Cryptology	2009	DBLP DOI BibTeX RDF	Unbalanced expander graphs, Timestamping, Randomness extractors, Bounded-storage model
1	Dorit Aharonov, Itai Arad, Zeph Landau, Umesh V. Vazirani	The detectability lemma and quantum gap amplification.	STOC	2009	DBLP DOI BibTeX RDF	QMA, detectability lemma, gap amplification, local hamiltonians, quantum computation, PCP
1	Sanjeev Arora, Constantinos Daskalakis, David Steurer	Message passing algorithms and improved LP decoding.	STOC	2009	DBLP DOI BibTeX RDF	lp decoding, min-sum algorithm, ldpc codes, message-passing algorithms
1	Klim Efremenko, Omer Reingold	How Well Do Random Walks Parallelize?.	APPROX-RANDOM	2009	DBLP DOI BibTeX RDF	Markov Chains, Random Walks
1	Navin Goyal, Neil Olver, F. Bruce Shepherd	Dynamic vs. Oblivious Routing in Network Design.	ESA	2009	DBLP DOI BibTeX RDF
1	Benjamin Doerr, Tobias Friedrich, Thomas Sauerwald	Quasirandom Rumor Spreading: Expanders, Push vs. Pull, and Robustness.	ICALP	2009	DBLP DOI BibTeX RDF
1	Sina Jafarpour	Efficient Compressed Sensing using Lossless Expander Graphs with Fast Bilateral Quantum Recovery Algorithm	CoRR	2008	DBLP BibTeX RDF
1	Sina Jafarpour, Weiyu Xu, Babak Hassibi, A. Robert Calderbank	Efficient and Robust Compressed Sensing using High-Quality Expander Graphs	CoRR	2008	DBLP BibTeX RDF
1	Carlos Ansótegui, Ramón Béjar, Cèsar Fernández, Carles Mateu	Hard SAT and CSP instances with Expander Graphs.	ISAIM	2008	DBLP BibTeX RDF
1	Carlos Ansótegui, Ramón Béjar, Cèsar Fernández, Carles Mateu	Generating Hard SAT/CSP Instances Using Expander Graphs.	AAAI	2008	DBLP BibTeX RDF
1	Bernard Chazelle, Wolfgang Johann Heinrich Mulzer	Markov incremental constructions.	Symposium on Computational Geometry	2008	DBLP DOI BibTeX RDF	clarkson-shor bound, randomized incremental constructions, expander graphs
1	Sanjeev Arora, Subhash Khot, Alexandra Kolla, David Steurer, Madhur Tulsiani, Nisheeth K. Vishnoi	Unique games on expanding constraint graphs are easy: extended abstract.	STOC	2008	DBLP DOI BibTeX RDF	approximation algorithms, semidefinite programming, expander graphs
1	Daniel A. Spielman, Nikhil Srivastava	Graph sparsification by effective resistances.	STOC	2008	DBLP DOI BibTeX RDF	electrical flows, random sampling, spectral graph theory
1	Jure Leskovec, Kevin J. Lang, Anirban Dasgupta, Michael W. Mahoney	Statistical properties of community structure in large social and information networks.	WWW	2008	DBLP DOI BibTeX RDF	social networks, random walks, graph partitioning, community structure, conductance
1	Eldar Fischer, Oded Lachish, Ilan Newman, Arie Matsliah, Orly Yahalom	On the Query Complexity of Testing Orientations for Being Eulerian.	APPROX-RANDOM	2008	DBLP DOI BibTeX RDF
1	Angsheng Li, Linqing Tang	Derandomizing Graph Tests for Homomorphism.	TAMC	2008	DBLP DOI BibTeX RDF
1	Alexander Healy	Randomness-Efficient Sampling within NC1.	Computational Complexity	2008	DBLP DOI BibTeX RDF	68Q15, 68R10, Subject classification. 68Q10
1	Shashi Kiran Chilappagari, Bane V. Vasic	Reliable Memories Built from Unreliable Components Based on Expander Graphs	CoRR	2007	DBLP BibTeX RDF
1	David P. Woodruff	Revisiting the Efficiency of Malicious Two-Party Computation.	EUROCRYPT	2007	DBLP DOI BibTeX RDF	malicious model, efficiency, expander graphs, secure function evaluation
1	James Aspnes, Navin Rustagi, Jared Saia	Worm Versus Alert: Who Wins in a Battle for Control of a Large-Scale Network?.	OPODIS	2007	DBLP DOI BibTeX RDF	Self-certifying alert, epidemic processes, peer-to-peer, overlay network, worm, expander graphs
1	Salil P. Vadhan	The unified theory of pseudorandomness: guest column.	SIGACT News	2007	DBLP DOI BibTeX RDF
1	Venkatesan Guruswami	List Decoding and Pseudorandom Constructions.	AAECC	2007	DBLP DOI BibTeX RDF
1	Ueli M. Maurer, Stefano Tessaro	Domain Extension of Public Random Functions: Beyond the Birthday Barrier.	CRYPTO	2007	DBLP DOI BibTeX RDF
1	Shishir Nagaraja	Anonymity in the Wild: Mixes on Unstructured Networks.	Privacy Enhancing Technologies	2007	DBLP DOI BibTeX RDF
1	Elchanan Mossel, Sébastien Roch	Slow emergence of cooperation for win-stay lose-shift on trees.	Machine Learning	2007	DBLP DOI BibTeX RDF	Games on graphs, Prisoner’s dilemma game, Win-Stay Lose-Shift, Oriented percolation, Emergence of cooperation, Learning
1	Eyal Rozenman, Aner Shalev, Avi Wigderson	Iterative Construction of Cayley Expander Graphs.	Theory of Computing	2006	DBLP DOI BibTeX RDF
1	Denis Xavier Charles, Eyal Z. Goren, Kristin Lauter	Cryptographic hash functions from expander graphs.	IACR Cryptology ePrint Archive	2006	DBLP BibTeX RDF
1	Laurent Massoulié, Erwan Le Merrer, Anne-Marie Kermarrec, Ayalvadi J. Ganesh	Peer counting and sampling in overlay networks: random walk methods.	PODC	2006	DBLP DOI BibTeX RDF	sampling, random walks, peer-to-peer systems, expander graphs
1	Omer Reingold, Luca Trevisan, Salil P. Vadhan	Pseudorandom walks on regular digraphs and the RL vs. L problem.	STOC	2006	DBLP DOI BibTeX RDF	universal traversal sequence, zig-zag product, derandomization, expander graphs, mixing time, space-bounded computation
1	Mette Berger, Esben Rune Hansen, Rasmus Pagh, Mihai Patrascu, Milan Ruzic, Peter Tiedemann	Deterministic load balancing and dictionaries in the parallel disk model.	SPAA	2006	DBLP DOI BibTeX RDF	parallel disk model, hashing, dictionary, expander graph, deterministic
1	Amnon Ta-Shma, Christopher Umans	Better lossless condensers through derandomized curve samplers.	FOCS	2006	DBLP DOI BibTeX RDF
1	Eran Rom, Amnon Ta-Shma	Improving the Alphabet-Size in Expander-Based Code Constructions.	IEEE Transactions on Information Theory	2006	DBLP DOI BibTeX RDF
1	Alexander Healy	Randomness-Efficient Sampling Within NC1.	APPROX-RANDOM	2006	DBLP DOI BibTeX RDF
1	Subhas Kumar Ghosh	On Optimality of Key Pre-distribution Schemes for Distributed Sensor Networks.	ESAS	2006	DBLP DOI BibTeX RDF
1	Jaikumar Radhakrishnan	Gap Amplification in PCPs Using Lazy Random Walks.	ICALP	2006	DBLP DOI BibTeX RDF
1	Vicky Choi, Navin Goyal	An Efficient Approximation Algorithm for Point Pattern Matching Under Noise.	LATIN	2006	DBLP DOI BibTeX RDF
1	Yonatan Bilu, Nathan Linial	Lifts, Discrepancy and Nearly Optimal Spectral Gap*.	Combinatorica	2006	DBLP DOI BibTeX RDF	Mathematics Subject Classification (2000): 05C22, 05C35, 05C80, 05C50
1	Peter Mahlmann, Christian Schindelhauer	Peer-to-peer networks based on random transformations of connected regular undirected graphs.	SPAA	2005	DBLP DOI BibTeX RDF	distributed algorithms, peer-to-peer networks, random graphs, expander graphs
1	David Jao, Stephen D. Miller, Ramarathnam Venkatesan	Do All Elliptic Curves of the Same Order Have the Same Difficulty of Discrete Log?	ASIACRYPT	2005	DBLP DOI BibTeX RDF	random reducibility, modular forms, L-functions, generalized Riemann hypothesis, elliptic curves, expanders, Ramanujan graphs, isogenies, rapid mixing, discrete log
1	Nedialko B. Dimitrov, C. Greg Plaxton	Optimal Cover Time for a Graph-Based Coupon Collector Process.	ICALP	2005	DBLP DOI BibTeX RDF
1	Yevgeniy Dodis, Adam Smith	Entropic Security and the Encryption of High Entropy Messages.	TCC	2005	DBLP DOI BibTeX RDF
1	Venkatesan Guruswami	Better extractors for better codes?	STOC	2004	DBLP DOI BibTeX RDF	error-correcting codes, expander graphs, pseudorandomness, list decoding, randomness extractors
1	Chi-Jen Lu	Encryption against Storage-Bounded Adversaries from On-Line Strong Extractors.	J. Cryptology	2004	DBLP DOI BibTeX RDF	Everlasting security, List-decodable codes, Expander graphs, Randomness extractors, Bounded-storage model
1	Salil P. Vadhan	Constructing Locally Computable Extractors and Cryptosystems in the Bounded-Storage Model.	J. Cryptology	2004	DBLP DOI BibTeX RDF	Everlasting security, Space-bounded adversaries, Averaging samplers, Expander graphs, Extractors, Unconditional security, Bounded-storage model
1	Alessandro Panconesi, Jaikumar Radhakrishnan	Expansion properties of (secure) wireless networks.	SPAA	2004	DBLP DOI BibTeX RDF	security, ad hoc networks, wireless networks, distributed algorithms, connectivity, expanders
1	Bogdan S. Chlebus, Dariusz R. Kowalski, Alexander A. Shvartsman	Collective asynchronous reading with polylogarithmic worst-case overhead.	STOC	2004	DBLP DOI BibTeX RDF	graph expansion, distributed algorithms, collect
1	Dan Gutfreund, Emanuele Viola	Fooling Parity Tests with Parity Gates.	APPROX-RANDOM	2004	DBLP DOI BibTeX RDF
1	Douglas E. Carroll, Ashish Goel	Lower Bounds for Embedding into Distributions over Excluded Minor Graph Families.	ESA	2004	DBLP DOI BibTeX RDF
1	Venkatesan Guruswami, Piotr Indyk	Linear time encodable and list decodable codes.	STOC	2003	DBLP DOI BibTeX RDF	adversarial noise model, linear time computation, expander graphs, list decoding, spectral partitioning
1	Christos Gkantsidis, Milena Mihail, Amin Saberi	Conductance and congestion in power law graphs.	SIGMETRICS	2003	DBLP DOI BibTeX RDF	powerlaw graphs, routing, congestion, expansion, internet topology, conductance
1	Yair Bartal, Manor Mendel	Multi-embedding and path approximation of metric spaces.	SODA	2003	DBLP DOI BibTeX RDF
1	Eli Ben-Sasson, Madhu Sudan, Salil P. Vadhan, Avi Wigderson	Randomness-efficient low degree tests and short PCPs via epsilon-biased sets.	STOC	2003	DBLP DOI BibTeX RDF	property testing, probabilistically checkable proofs, locally testable codes, linearity testing, low degree testing
1	Sergey Bobkov, Prasad Tetali	Modified log-sobolev inequalities, mixing and hypercontractivity.	STOC	2003	DBLP DOI BibTeX RDF	entropy decay, sobolev inequalities, spectral gap
1	George Danezis	Mix-Networks with Restricted Routes.	Privacy Enhancing Technologies	2003	DBLP DOI BibTeX RDF	mix cascades, anonymity, traffic analysis, Mix networks
1	Michael R. Capalbo, Omer Reingold, Salil P. Vadhan, Avi Wigderson	Randomness conductors and constant-degree lossless expanders.	STOC	2002	DBLP DOI BibTeX RDF	expander graphs, extractors, condensers, graph products
1	Michael R. Capalbo, Omer Reingold, Salil P. Vadhan, Avi Wigderson	Randomness Conductors and Constant-Degree Lossless Expanders. (PDF / PS)	IEEE Conference on Computational Complexity	2002	DBLP DOI BibTeX RDF	expander graphs, extractors, condensers, graph products
1	Alexander Gamburd, Igor Pak	Expansion of product replacement graphs.	SODA	2002	DBLP DOI BibTeX RDF
1	Salil P. Vadhan	Randomness Extractors and their Many Guises.	FOCS	2002	DBLP DOI BibTeX RDF
1	K. V. M. Naidu, H. Ramesh	Lower Bounds for Embedding Graphs into Graphs of Smaller Characteristic.	FSTTCS	2002	DBLP DOI BibTeX RDF
1	Jan Johannsen, N. S. Narayanaswamy	An Optimal Lower Bound for Resolution with 2-Conjunctions.	MFCS	2002	DBLP DOI BibTeX RDF
1	Amnon Ta-Shma, Christopher Umans, David Zuckerman	Loss-less condensers, unbalanced expanders, and extractors.	STOC	2001	DBLP DOI BibTeX RDF
1	Salil P. Vadhan	Order in Pseudorandomness.	RANDOM-APPROX	2001	DBLP DOI BibTeX RDF
1	Oded Goldreich	Candidate One-Way Functions Based on Expander Graphs	Electronic Colloquium on Computational Complexity (ECCC)	2000	DBLP BibTeX RDF
1	Oded Goldreich	Candidate One-Way Functions Based on Expander Graphs.	IACR Cryptology ePrint Archive	2000	DBLP BibTeX RDF
1	Alan M. Frieze	Edge-Disjoint Paths in Expander Graphs.	SIAM J. Comput.	2000	DBLP DOI BibTeX RDF
1	Alan M. Frieze	Edge-disjoint paths in expander graphs.	SODA	2000	DBLP DOI BibTeX RDF
1	Andrei Z. Broder, Alan M. Frieze, Eli Upfal	Static and Dynamic Path Selection on Expander Graphs: A Random Walk Approach.	Random Struct. Algorithms	1999	DBLP DOI BibTeX RDF
1	Ziv Bar-Yossef, Oded Goldreich, Avi Wigderson	Deterministic Amplification of Space-Bounded Probabilistic Algorithms. (PDF / PS)	IEEE Conference on Computational Complexity	1999	DBLP DOI BibTeX RDF	space bounded randomized computation, deterministic amplification, expander graphs
1	Jacobo Torán	Lower Bounds for Space in Resolution.	CSL	1999	DBLP DOI BibTeX RDF	lower bounds, Resolution, space, complexity measures, pebbling game