Search results for "expander"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
82	Satyen Kale, Yuval Peres, C. Seshadhri 0001	Noise Tolerance of Expanders and Sublinear Expander Reconstruction.	FOCS	2008	DBLP DOI BibTeX RDF
81	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
76	Alexander Gamburd, Igor Pak	Expansion of product replacement graphs.	SODA	2002	DBLP BibTeX RDF
75	Denis Xavier Charles, Kristin E. Lauter, Eyal Z. Goren	Cryptographic Hash Functions from Expander Graphs.	J. Cryptol.	2009	DBLP DOI BibTeX RDF	Supersingular elliptic curves, Elliptic curve cryptography, Expander graphs, Cryptographic hash functions, Ramanujan graphs, Isogenies
75	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
69	Alexander Barg, Gilles Zémor	Distance properties of expander codes.	IEEE Trans. Inf. Theory	2006	DBLP DOI BibTeX RDF
62	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
62	Heeralal Janwa	Good Expander Graphs and Expander Codes: Parameters and Decoding.	AAECC	2003	DBLP DOI BibTeX RDF
57	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
57	Katalin Friedl, Shi-Chun Tsai	Recycling random bits in parallel.	HICSS (2)	1995	DBLP DOI BibTeX RDF	pseudo-random bits, block concatenation, random bit recycling, short integers, independently generated bit segments, optimal speedup, parallel algorithms, parallel algorithm, random walk, random number generation, arithmetic, expander graph, randomised algorithms, arithmetic operations
56	Dawn Xiaodong Song, J. D. Tygar, David Zuckerman	Expander Graphs for Digital Stream Authentication and Robust Overlay Networks.	S&P	2002	DBLP DOI BibTeX RDF
56	Sotiris E. Nikoletseas, Paul G. Spirakis	Expander Properties in Random Regular Graphs with Edge Faults.	STACS	1995	DBLP DOI BibTeX RDF
56	Michael Sipser, Daniel A. Spielman	Expander Codes	FOCS	1994	DBLP DOI BibTeX RDF	logarithmic time parallel decoding algorithms, expander codes, linear error-correcting codes, linear time sequential decoding algorithms, expander graphs
51	Erik Schüler, Adão Antônio de Souza Jr., Luigi Carro	Spare Parts in Analog Circuits: A Filter Example.	DFT	2007	DBLP DOI BibTeX RDF
50	Harold N. Gabow	Using expander graphs to find vertex connectivity.	J. ACM	2006	DBLP DOI BibTeX RDF	graphs, Expander graphs, vertex connectivity
44	Joshua D. Batson, Daniel A. Spielman, Nikhil Srivastava	Twice-ramanujan sparsifiers.	STOC	2009	DBLP DOI BibTeX RDF	expander graphs, spectral graph theory
44	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
44	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
44	Sanjeev Arora, Satish Rao, Umesh V. Vazirani	Expander flows, geometric embeddings and graph partitioning.	J. ACM	2009	DBLP DOI BibTeX RDF	Graph partitioning, semidefinite programs, multicommodity flows, expanders, expansion, graph separators
44	Venkatesan Guruswami	Guest column: error-correcting codes and expander graphs.	SIGACT News	2004	DBLP DOI BibTeX RDF
44	Sanjeev Arora, Satish Rao, Umesh V. Vazirani	Expander flows, geometric embeddings and graph partitioning.	STOC	2004	DBLP DOI BibTeX RDF
44	Shimon Even, Ami Litman	A Unified Scheme for Routing in Expander Based Networks.	CIAC	1994	DBLP DOI BibTeX RDF
38	Shlomi Dolev, Nir Tzachar	Spanders: distributed spanning expanders.	SAC	2010	DBLP DOI BibTeX RDF	self-orgenization, self-stabilization, expanders
38	Alessandro Warth, Milan Stanojevic, Todd D. Millstein	Statically scoped object adaptation with expanders.	OOPSLA	2006	DBLP DOI BibTeX RDF	object adaptation, expanders, modular typechecking
38	Michael K. Reiter, Asad Samar, Chenxi Wang	Distributed Construction of a Fault-Tolerant Network from a Tree.	SRDS	2005	DBLP DOI BibTeX RDF
37	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
37	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
37	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
32	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
32	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
32	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
32	Nathan Keller, Stephen D. Miller, Ilya Mironov, Ramarathnam Venkatesan	MV3: A New Word Based Stream Cipher Using Rapid Mixing and Revolving Buffers.	CT-RSA	2007	DBLP DOI BibTeX RDF	cryptanalysis, stream cipher, random walks, expander graph
32	Venkatesan Guruswami, Christopher Umans, Salil P. Vadhan	Unbalanced Expanders and Randomness Extractors from Parvaresh-Vardy Codes.	CCC	2007	DBLP DOI BibTeX RDF	error-correcting codes, expander graphs, condensers, list decoding, randomness extractors
32	Stephen D. Miller, Ramarathnam Venkatesan	Spectral Analysis of Pollard Rho Collisions.	ANTS	2006	DBLP DOI BibTeX RDF	Pollard Rho algorithm, collision time, random walk, spectral analysis, discrete logarithm, expander graph, mixing time
32	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
32	Venkatesan Guruswami	Better extractors for better codes?	STOC	2004	DBLP DOI BibTeX RDF	error-correcting codes, expander graphs, pseudorandomness, list decoding, randomness extractors
32	Michael R. Capalbo, Omer Reingold, Salil P. Vadhan, Avi Wigderson	Randomness Conductors and Constant-Degree Lossless Expanders.	CCC	2002	DBLP DOI BibTeX RDF	expander graphs, extractors, condensers, graph products
32	Eero Lassila	A Macro Expansion Approach to Embedded Processor Code Generation.	EUROMICRO	1996	DBLP DOI BibTeX RDF	macro expansion approach, embedded processor code generation, embedded special-purpose processors, retargetable assembly-code-level macro expander, program flow analysis, hierarchical macro libraries, compiler writer, assembly language programmer, computer architecture
31	Sumit Ganguly	Data Stream Algorithms via Expander Graphs.	ISAAC	2008	DBLP DOI BibTeX RDF
31	Tom Høholdt	Codes from Expander Graphs.	ICMCTA	2008	DBLP DOI BibTeX RDF
31	Eran Rom, Amnon Ta-Shma	Improving the Alphabet-Size in Expander-Based Code Constructions.	IEEE Trans. Inf. Theory	2006	DBLP DOI BibTeX RDF
31	Alexei E. Ashikhmin, Vitaly Skachek	Decoding of Expander Codes at Rates Close to Capacity.	IEEE Trans. Inf. Theory	2006	DBLP DOI BibTeX RDF
31	Ron M. Roth, Vitaly Skachek	Improved Nearly-MDS Expander Codes.	IEEE Trans. Inf. Theory	2006	DBLP DOI BibTeX RDF
31	Jin-yi Cai	Essentially Every Unimodular Matrix Defines an Expander.	Theory Comput. Syst.	2003	DBLP DOI BibTeX RDF
31	Jin-yi Cai	Essentially Every Unimodular Matrix Defines and Expander.	ISAAC	2000	DBLP DOI BibTeX RDF
31	Alan M. Frieze	Disjoint Paths in Expander Graphs via Random Walks: A Short Survey.	RANDOM	1998	DBLP DOI BibTeX RDF
31	Matthew J. Katz, Micha Sharir	An Expander-Based Approach to Geometric Optimization.	SCG	1993	DBLP DOI BibTeX RDF
25	Navin Goyal, Luis Rademacher, Santosh S. Vempala	Expanders via random spanning trees.	SODA	2009	DBLP DOI BibTeX RDF
25	Alexander Healy	Randomness-Efficient Sampling within NC1.	Comput. Complex.	2008	DBLP DOI BibTeX RDF	68Q15, 68R10, Subject classification. 68Q10
25	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
25	Moni Naor, Udi Wieder	Novel architectures for P2P applications: The continuous-discrete approach.	ACM Trans. Algorithms	2007	DBLP DOI BibTeX RDF	routing, Peer-to-peer networks
25	Shishir Nagaraja	Anonymity in the Wild: Mixes on Unstructured Networks.	Privacy Enhancing Technologies	2007	DBLP DOI BibTeX RDF
25	Yonatan Bilu, Nathan Linial	Lifts, Discrepancy and Nearly Optimal Spectral Gap*.	Comb.	2006	DBLP DOI BibTeX RDF	Mathematics Subject Classification (2000): 05C22, 05C35, 05C80, 05C50
25	Domingos Dellamonica Jr., Yoshiharu Kohayakawa	An algorithmic Friedman--Pippenger theorem on tree embeddings and applications to routing.	SODA	2006	DBLP DOI BibTeX RDF
25	Alexander Healy	Randomness-Efficient Sampling Within NC1.	APPROX-RANDOM	2006	DBLP DOI BibTeX RDF
25	Jon Feldman, Clifford Stein 0001	LP decoding achieves capacity.	SODA	2005	DBLP BibTeX RDF
25	Avi Wigderson, David Xiao	A Randomness-Efficient Sampler for Matrix-valued Functions and Applications.	FOCS	2005	DBLP DOI BibTeX RDF
25	Sanjeev Arora, Elad Hazan, Satyen Kale	0(sqrt (log n)) Approximation to SPARSEST CUT in Õ(n2) Time.	FOCS	2004	DBLP DOI BibTeX RDF
25	Moni Naor, Udi Wieder	Novel architectures for P2P applications: the continuous-discrete approach.	SPAA	2003	DBLP DOI BibTeX RDF	fault tolerance, distributed systems, peer-to-peer, hash tables
25	Eli Ben-Sasson	Hard examples for the bounded depth Frege proof system.	Comput. Complex.	2002	DBLP DOI BibTeX RDF	Mathematics Subject Classification (2000). 03F20
25	Anna Östlin, Rasmus Pagh	One-Probe Search.	ICALP	2002	DBLP DOI BibTeX RDF
25	Eli Ben-Sasson	Hard examples for bounded depth frege.	STOC	2002	DBLP DOI BibTeX RDF
25	K. V. M. Naidu, H. Ramesh	Lower Bounds for Embedding Graphs into Graphs of Smaller Characteristic.	FSTTCS	2002	DBLP DOI BibTeX RDF
25	Eli Ben-Sasson, Nicola Galesi	Space Complexity of Random Formulae in Resolution.	CCC	2001	DBLP DOI BibTeX RDF
25	Uwe Schöning	Resolution Proofs, Exponential Bounds, and Kolmogorov Complexity.	MFCS	1997	DBLP DOI BibTeX RDF
25	Maher E. Rizkalla, Richard L. Aldridge, Nadeem A. Khan, Harry C. Gundrum	A CMOS VLSI Implementation of an NxN Multiplexing Circuitry for ATM Applications.	Great Lakes Symposium on VLSI	1996	DBLP DOI BibTeX RDF
25	Thomas H. Spencer	Parallel matching on expanders.	SPDP	1991	DBLP DOI BibTeX RDF
19	Thomas Sauerwald	Expansion and the cover time of parallel random walks.	PODC	2010	DBLP DOI BibTeX RDF	random walks, expander, expansion, cover time
19	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
19	Tal Moran, Ronen Shaltiel, Amnon Ta-Shma	Non-interactive Timestamping in the Bounded-Storage Model.	J. Cryptol.	2009	DBLP DOI BibTeX RDF	Unbalanced expander graphs, Timestamping, Randomness extractors, Bounded-storage model
19	Bernard Chazelle, Wolfgang Johann Heinrich Mulzer	Markov incremental constructions.	SCG	2008	DBLP DOI BibTeX RDF	clarkson-shor bound, randomized incremental constructions, expander graphs
19	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
19	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
19	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
19	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
19	Bogdan S. Chlebus, Dariusz R. Kowalski	Cooperative asynchronous update of shared memory.	STOC	2005	DBLP DOI BibTeX RDF	problem Write-All, read and write register, work efficiency, distributed algorithm, expander, asynchrony, disperser
19	Chi-Jen Lu	Encryption against Storage-Bounded Adversaries from On-Line Strong Extractors.	J. Cryptol.	2004	DBLP DOI BibTeX RDF	Everlasting security, List-decodable codes, Expander graphs, Randomness extractors, Bounded-storage model
19	Salil P. Vadhan	Constructing Locally Computable Extractors and Cryptosystems in the Bounded-Storage Model.	J. Cryptol.	2004	DBLP DOI BibTeX RDF	Everlasting security, Space-bounded adversaries, Averaging samplers, Expander graphs, Extractors, Unconditional security, Bounded-storage model
19	Bogdan S. Chlebus, Dariusz R. Kowalski	A better wake-up in radio networks.	PODC	2004	DBLP DOI BibTeX RDF	radio synchronizer, wake-up problem, ad-hoc network, synchronization, leader election, expander, multi-hop radio network
19	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
19	Toshinori Yamada, Shuichi Ueno	Optimal fault-tolerant linear arrays.	SPAA	2003	DBLP DOI BibTeX RDF	fault-tolerant graph, magnifier, expander, linear array
19	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
19	Ziv Bar-Yossef, Oded Goldreich 0001, Avi Wigderson	Deterministic Amplification of Space-Bounded Probabilistic Algorithms.	CCC	1999	DBLP DOI BibTeX RDF	space bounded randomized computation, deterministic amplification, expander graphs
19	Michael E. Saks, Aravind Srinivasan, Shiyu Zhou	Explicit OR-Dispersers with Polylogarithmic Degree.	J. ACM	1998	DBLP DOI BibTeX RDF	hashing lemmas, imperfect sources of randomness, measures of information, hardness of approximation, derandomization, expander graphs, time-space tradeoffs, pseudo-random generators, explicit constructions, randomized computation
19	Dima Grigoriev	Tseitin's Tautologies and Lower Bounds for Nullstellensatz Proofs.	FOCS	1998	DBLP DOI BibTeX RDF	Nullstellensatz proofs, Tseitin's tautologies, lower bounds, expander
19	Nabil Kahalé	Eigenvalues and Expansion of Regular Graphs.	J. ACM	1995	DBLP DOI BibTeX RDF	induced subgraphs, selection networks, load balancing, random walks, eigenvalues, expander graphs, Ramanujan graphs
19	Aravind Srinivasan, David Zuckerman	Computing with Very Weak Random Sources	FOCS	1994	DBLP DOI BibTeX RDF	randomness-efficient Leftover Hash Lemma, very weak random sources, RP algorithms simulation, R-bit string, BPP simulations, Chor-Goldreich sources, expander constructions, probability, hardness, time-space tradeoffs, min-entropy
19	Andrei Z. Broder, Anna R. Karlin	Bounds on the Cover Time (Preliminary Version)	FOCS	1988	DBLP DOI BibTeX RDF	regular expander graphs, connected unidirected graph, lower bounds, Markov chain, random walk, upper bounds, eigenvalues, vertices, particle, cover time, neighbors
18	Mohamad Al Adraa, Chadi Assi, Mohammed Almekhlafi, Maurice Khabbaz, Vladimir Pelekhaty, Michael Y. Frankel	Comprehensive Performance and Robustness Analysis of Expander-Based Data Centers.	IEEE Trans. Netw. Serv. Manag.	2024	DBLP DOI BibTeX RDF
18	Oded Goldreich 0001	On locally-characterized expander graphs (a survey).	Electron. Colloquium Comput. Complex.	2024	DBLP BibTeX RDF
18	Silas Richelson, Sourya Roy	Analyzing Ta-Shma's Code via the Expander Mixing Lemma.	IEEE Trans. Inf. Theory	2024	DBLP DOI BibTeX RDF
18	Amir Abboud, Nathan Wallheimer	Worst-Case to Expander-Case Reductions: Derandomized and Generalized.	CoRR	2024	DBLP DOI BibTeX RDF
18	Aurelio L. Sulser, Maximilian Probst Gutenberg	A Simple and Near-Optimal Algorithm for Directed Expander Decompositions.	CoRR	2024	DBLP DOI BibTeX RDF
18	Kyungsan Kim, Hyunseok Kim, Jinin So, Wonjae Lee, Junhyuk Im, Sungjoo Park, Jeonghyeon Cho, Hoyoung Song	SMT: Software-Defined Memory Tiering for Heterogeneous Computing Systems With CXL Memory Expander.	IEEE Micro	2023	DBLP DOI BibTeX RDF
18	Elette Boyle, Ran Cohen, Deepesh Data, Pavel Hubácek	Must the Communication Graph of MPC Protocols be an Expander?	J. Cryptol.	2023	DBLP DOI BibTeX RDF
18	Carlos Andrés Mugruza-Vassallo	A "fractal" expander-compressor-supplier formative research method on array processing.	Educ. Inf. Technol.	2023	DBLP DOI BibTeX RDF
18	Xue Chen, Kuan Cheng, Xin Li 0006, Minghui Ouyang	Improved Decoding of Expander Codes.	IEEE Trans. Inf. Theory	2023	DBLP DOI BibTeX RDF
18	Oindrila Deb, Arpan Mukhopadhyay	Biased Consensus Dynamics on Regular Expander Graphs.	CoRR	2023	DBLP DOI BibTeX RDF
18	Dongrun Cai, Xue Chen, Pan Peng 0001	Effective Resistances in Non-Expander Graphs.	CoRR	2023	DBLP DOI BibTeX RDF
18	Fernando Granha Jeronimo, Shashank Srivastava, Madhur Tulsiani	List Decoding of Tanner and Expander Amplified Codes from Distance Certificates.	CoRR	2023	DBLP DOI BibTeX RDF