Search results for "expander"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
18	Rajesh K. Pankaj	All-Optical Network Topologies Based on Expander Graphs.	J. High Speed Networks	1995	DBLP DOI BibTeX RDF
18	Andrei Z. Broder, Alan M. Frieze, Eli Upfal	Existence and Construction of Edge-Disjoint Paths on Expander Graphs.	SIAM J. Comput.	1994	DBLP DOI BibTeX RDF
18	Shlomo Hoory, Avi Wigderson	Universal Traversal Sequences for Expander Graphs.	Inf. Process. Lett.	1993	DBLP DOI BibTeX RDF
18	Pierre Kelsen	Fast Parallel Matching in Expander Graphs.	SPAA	1993	DBLP DOI BibTeX RDF
18	Nabil Kahalé	Expander graphs.		1993	RDF
18	Andrei Z. Broder, Alan M. Frieze, Eli Upfal	Existence and Construction of Edge Disjoint Paths on Expander Graphs	STOC	1992	DBLP DOI BibTeX RDF
18	Ronitt Rubinfeld	The Cover Time of a Regular Expander is O(n log n).	Inf. Process. Lett.	1990	DBLP DOI BibTeX RDF
18	David Peleg, Eli Upfal	Constructng disjoint paths on expander graphs.	Comb.	1989	DBLP DOI BibTeX RDF
18	David Peleg, Eli Upfal	Constructing Disjoint Paths on Expander Graphs (Extended Abstract)	STOC	1987	DBLP DOI BibTeX RDF
13	Sherif Sakr, Ahmed Awad 0001	A framework for querying graph-based business process models.	WWW	2010	DBLP DOI BibTeX RDF	querying business process - bpmn, process models
13	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
13	Stefano Pini, Sangmok Han, David R. Wallace	Text entry for mobile devices using ad-hoc abbreviation.	AVI	2010	DBLP DOI BibTeX RDF	support vector machine, mobile devices, Hidden Markov model, text input, auto-completion, abbreviation
13	Alexandra Kolla, Yury Makarychev, Amin Saberi, Shang-Hua Teng	Subgraph sparsification and nearly optimal ultrasparsifiers.	STOC	2010	DBLP DOI BibTeX RDF	algebraic connectivity, graph sparsification, ultrasparsifiers, approximation algorithms
13	James Aspnes, Udi Wieder	The expansion and mixing time of skip graphs with applications.	Distributed Comput.	2009	DBLP DOI BibTeX RDF
13	Rohit Khandekar, Satish Rao, Umesh V. Vazirani	Graph partitioning using single commodity flows.	J. ACM	2009	DBLP DOI BibTeX RDF	Edge-separator, single commodity max-flow, sparse cut, spectral method
13	Jure Leskovec	Networks, communities and kronecker products.	CIKM-CNIKM	2009	DBLP DOI BibTeX RDF	kronecker graphs, network community profile, social networks, graph partitioning, community structure, conductance
13	James Aspnes, Keren Censor	Approximate shared-memory counting despite a strong adversary.	SODA	2009	DBLP DOI BibTeX RDF
13	Navin Goyal, Neil Olver, F. Bruce Shepherd	Dynamic vs. Oblivious Routing in Network Design.	ESA	2009	DBLP DOI BibTeX RDF
13	Benjamin Doerr, Tobias Friedrich 0001, Thomas Sauerwald	Quasirandom Rumor Spreading: Expanders, Push vs. Pull, and Robustness.	ICALP (1)	2009	DBLP DOI BibTeX RDF
13	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
13	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
13	Klim Efremenko, Omer Reingold	How Well Do Random Walks Parallelize?.	APPROX-RANDOM	2009	DBLP DOI BibTeX RDF	Markov Chains, Random Walks
13	Aram W. Harrow, Richard Andrew Low	Efficient Quantum Tensor Product Expanders and k-Designs.	APPROX-RANDOM	2009	DBLP DOI BibTeX RDF
13	Eli Ben-Sasson, Michael Viderman	Composition of Semi-LTCs by Two-Wise Tensor Products.	APPROX-RANDOM	2009	DBLP DOI BibTeX RDF
13	Venkatesan Guruswami, Valentine Kabanets	Hardness Amplification via Space-Efficient Direct Products.	Comput. Complex.	2008	DBLP DOI BibTeX RDF	94B35, 68Q25, 94B05, 68P30, Subject classification. 68Q17
13	Venkatesan Guruswami, Atri Rudra	Explicit Codes Achieving List Decoding Capacity: Error-Correction With Optimal Redundancy.	IEEE Trans. Inf. Theory	2008	DBLP DOI BibTeX RDF
13	Richard C. Wang, William W. Cohen	Iterative Set Expansion of Named Entities Using the Web.	ICDM	2008	DBLP DOI BibTeX RDF
13	László Babai, Nikolay Nikolov, László Pyber	Product growth and mixing in finite groups.	SODA	2008	DBLP BibTeX RDF
13	Jure Leskovec, Kevin J. Lang, Anirban Dasgupta 0001, 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
13	Angsheng Li, Linqing Tang	Derandomizing Graph Tests for Homomorphism.	TAMC	2008	DBLP DOI BibTeX RDF
13	Daniel A. Spielman, Nikhil Srivastava	Graph sparsification by effective resistances.	STOC	2008	DBLP DOI BibTeX RDF	electrical flows, random sampling, spectral graph theory
13	Eli Ben-Sasson, Michael Viderman	Tensor Products of Weakly Smooth Codes Are Robust.	APPROX-RANDOM	2008	DBLP DOI BibTeX RDF
13	Zeev Dvir, Amir Shpilka	Towards Dimension Expanders over Finite Fields.	CCC	2008	DBLP DOI BibTeX RDF	Cayley graphs, expanders, explicit constructions
13	Avraham Ben-Aroya, Oded Schwartz, Amnon Ta-Shma	Quantum Expanders: Motivation and Constructions.	CCC	2008	DBLP DOI BibTeX RDF	Quantum Expanders, Quantum Statistical Zero-Knowledge
13	Elchanan Mossel, Sébastien Roch	Slow emergence of cooperation for win-stay lose-shift on trees.	Mach. Learn.	2007	DBLP DOI BibTeX RDF	Games on graphs, Prisoner’s dilemma game, Win-Stay Lose-Shift, Oriented percolation, Emergence of cooperation, Learning
13	Irit Dinur	The PCP theorem by gap amplification.	J. ACM	2007	DBLP DOI BibTeX RDF	Gap amplification, PCP
13	Salil P. Vadhan	The unified theory of pseudorandomness: guest column.	SIGACT News	2007	DBLP DOI BibTeX RDF
13	Rainer Bye, Katja Luther, Seyit Ahmet Çamtepe, Tansu Alpcan, Sahin Albayrak, Bülent Yener	Decentralized Detector Generation in Cooperative Intrusion Detection Systems.	SSS	2007	DBLP DOI BibTeX RDF
13	Artur Czumaj, Christian Sohler	On testable properties in bounded degree graphs.	SODA	2007	DBLP BibTeX RDF
13	Noga Alon, Michael R. Capalbo	Finding Disjoint Paths in Expanders Deterministically and Online.	FOCS	2007	DBLP DOI BibTeX RDF
13	Artur Czumaj, Christian Sohler	Testing Expansion in Bounded-Degree Graphs.	FOCS	2007	DBLP DOI BibTeX RDF
13	Shankar Kalyanaraman, Christopher Umans	Algorithms for Playing Games with Limited Randomness.	ESA	2007	DBLP DOI BibTeX RDF
13	Venkatesan Guruswami	List Decoding and Pseudorandom Constructions.	AAECC	2007	DBLP DOI BibTeX RDF
13	Abraham D. Flaxman, Alan M. Frieze, Juan Vera 0001	A Geometric Preferential Attachment Model of Networks II.	WAW	2007	DBLP DOI BibTeX RDF
13	Ueli M. Maurer, Stefano Tessaro	Domain Extension of Public Random Functions: Beyond the Birthday Barrier.	CRYPTO	2007	DBLP DOI BibTeX RDF
13	Alexander Gamburd, Igor Pak	Expansion Of Product Replacement Graphs.	Comb.	2006	DBLP DOI BibTeX RDF	Mathematics Subject Classification (2000): 05C90, 20F99, 68R10
13	Todd P. Coleman, Anna H. Lee, Muriel Médard, Michelle Effros	Low-Complexity Approaches to Slepian-Wolf Near-Lossless Distributed Data Compression.	IEEE Trans. Inf. Theory	2006	DBLP DOI BibTeX RDF
13	Subhas Kumar Ghosh	On Optimality of Key Pre-distribution Schemes for Distributed Sensor Networks.	ESAS	2006	DBLP DOI BibTeX RDF
13	Amnon Ta-Shma, Christopher Umans	Better lossless condensers through derandomized curve samplers.	FOCS	2006	DBLP DOI BibTeX RDF
13	Arist Kojevnikov, Dmitry Itsykson	Lower Bounds of Static Lovász-Schrijver Calculus Proofs for Tseitin Tautologies.	ICALP (1)	2006	DBLP DOI BibTeX RDF
13	Jaikumar Radhakrishnan	Gap Amplification in PCPs Using Lazy Random Walks.	ICALP (1)	2006	DBLP DOI BibTeX RDF
13	Abraham D. Flaxman	Expansion and Lack Thereof in Randomly Perturbed Graphs.	WAW	2006	DBLP DOI BibTeX RDF
13	Lance Fortnow, Adam R. Klivans	Linear Advice for Randomized Logarithmic Space.	STACS	2006	DBLP DOI BibTeX RDF
13	Venkatesan Guruswami, Atri Rudra	Explicit capacity-achieving list-decodable codes.	STOC	2006	DBLP DOI BibTeX RDF	Zyablov bound, algebraic decoding, Reed-Solomon codes, list decoding, channel capacity
13	Irit Dinur	The PCP theorem by gap amplification.	STOC	2006	DBLP DOI BibTeX RDF	gap amplification, PCP
13	Rohit Khandekar, Satish Rao, Umesh V. Vazirani	Graph partitioning using single commodity flows.	STOC	2006	DBLP DOI BibTeX RDF	edge-separator, single commodity max-flow, sparse cut, spectral method
13	Irit Dinur, Madhu Sudan 0001, Avi Wigderson	Robust Local Testability of Tensor Products of LDPC Codes.	APPROX-RANDOM	2006	DBLP DOI BibTeX RDF
13	Vicky Choi, Navin Goyal	An Efficient Approximation Algorithm for Point Pattern Matching Under Noise.	LATIN	2006	DBLP DOI BibTeX RDF
13	Venkatesan Guruswami, Valentine Kabanets	Hardness Amplification Via Space-Efficient Direct Products.	LATIN	2006	DBLP DOI BibTeX RDF	error-correcting codes, expanders, Direct products, hardness amplification
13	Shi-Chun Tsai, Wen-Guey Tzeng, Hsin-Lung Wu	On the Jensen-Shannon Divergence and Variational Distance.	IEEE Trans. Inf. Theory	2005	DBLP DOI BibTeX RDF
13	Alexander Barg, Gilles Zémor	Concatenated codes: serial and parallel.	IEEE Trans. Inf. Theory	2005	DBLP DOI BibTeX RDF
13	Yevgeniy Dodis, Adam D. Smith	Entropic Security and the Encryption of High Entropy Messages.	TCC	2005	DBLP DOI BibTeX RDF
13	Nedialko B. Dimitrov, C. Greg Plaxton	Optimal Cover Time for a Graph-Based Coupon Collector Process.	ICALP	2005	DBLP DOI BibTeX RDF
13	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
13	Eran Rom, Amnon Ta-Shma	Improving the Alphabet-Size in High Noise, Almost Optimal Rate List Decodable Codes.	STACS	2005	DBLP DOI BibTeX RDF
13	James Aspnes, Udi Wieder	The expansion and mixing time of skip graphs with applications.	SPAA	2005	DBLP DOI BibTeX RDF	P2P, expansion
13	Roy Meshulam, Avi Wigderson	Expanders In Group Algebras.	Comb.	2004	DBLP DOI BibTeX RDF	Mathematics Subject Classification (2000): 05C25, 20C15
13	Douglas E. Carroll, Ashish Goel	Lower Bounds for Embedding into Distributions over Excluded Minor Graph Families.	ESA	2004	DBLP DOI BibTeX RDF
13	Venkatesan Guruswami, Piotr Indyk	Linear-Time List Decoding in Error-Free Settings: (Extended Abstract).	ICALP	2004	DBLP DOI BibTeX RDF
13	Luigi Dadda, Marco Macchetti, Jeff Owen	An ASIC design for a high speed implementation of the hash function SHA-256 (384, 512).	ACM Great Lakes Symposium on VLSI	2004	DBLP DOI BibTeX RDF	secure hash standard, hash function, data authentication
13	Eyal Rozenman, Aner Shalev, Avi Wigderson	A new family of Cayley expanders (?).	STOC	2004	DBLP DOI BibTeX RDF	zig-zag product, Cayley graphs, expanders
13	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
13	Dan Gutfreund, Emanuele Viola	Fooling Parity Tests with Parity Gates.	APPROX-RANDOM	2004	DBLP DOI BibTeX RDF
13	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
13	Heeralal Janwa, Arbind K. Lal	On Tanner Codes: Minimum Distance and Decoding.	Appl. Algebra Eng. Commun. Comput.	2003	DBLP DOI BibTeX RDF
13	Yair Bartal, Manor Mendel	Multi-embedding and path approximation of metric spaces.	SODA	2003	DBLP BibTeX RDF
13	Aris Anagnostopoulos, Adam Kirsch, Eli Upfal	Stability and Efficiency of a Random Local Load Balancing Protocol.	FOCS	2003	DBLP DOI BibTeX RDF
13	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
13	George Danezis	Mix-Networks with Restricted Routes.	Privacy Enhancing Technologies	2003	DBLP DOI BibTeX RDF	mix cascades, anonymity, traffic analysis, Mix networks
13	Andrea Maniero, Andrea Gerosa, Andrea Neviani	Performance optimization in micro-power, low-voltage log-domain filters in pure CMOS technology.	ISCAS (1)	2003	DBLP DOI BibTeX RDF
13	Sergey G. Bobkov, Prasad Tetali	Modified log-sobolev inequalities, mixing and hypercontractivity.	STOC	2003	DBLP DOI BibTeX RDF	entropy decay, sobolev inequalities, spectral gap
13	Eli Ben-Sasson, Madhu Sudan 0001, 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
13	Oded Goldreich 0001, Dana Ron	Property Testing in Bounded Degree Graphs.	Algorithmica	2002	DBLP DOI BibTeX RDF	Approximation algorithms, Randomized algorithms, Graph algorithms, Property testing
13	Salil P. Vadhan	Randomness Extractors and their Many Guises.	FOCS	2002	DBLP DOI BibTeX RDF
13	Jan Johannsen, N. S. Narayanaswamy	An Optimal Lower Bound for Resolution with 2-Conjunctions.	MFCS	2002	DBLP DOI BibTeX RDF
13	Jean-Daniel Boissonnat, Jurek Czyzowicz, Olivier Devillers, Mariette Yvinec	Circular Separability of Polygons.	Algorithmica	2001	DBLP DOI BibTeX RDF	Approximation algorithms, Randomized algorithms, Graph algorithms, Property testing
13	Salil P. Vadhan	Order in Pseudorandomness.	RANDOM-APPROX	2001	DBLP DOI BibTeX RDF
13	Amnon Ta-Shma, Christopher Umans, David Zuckerman	Loss-less condensers, unbalanced expanders, and extractors.	STOC	2001	DBLP DOI BibTeX RDF
13	Elena Dubrova, Peeter Ellervee, D. Michael Miller, Jon C. Muzio	TOP: An Algorithm for Three-Level Optimization of PLDs.	DATE	2000	DBLP DOI BibTeX RDF
13	Noga Alon, Haim Kaplan, Michael Krivelevich, Dahlia Malkhi, Julien P. Stern	Scalable Secure Storage when Half the System Is Faulty.	ICALP	2000	DBLP DOI BibTeX RDF
13	Oded Goldreich 0001, Dana Ron	A Sublinear Bipartiteness Tester for Bounded Degree Graphs.	Comb.	1999	DBLP DOI BibTeX RDF	AMS Subject Classification (1991) Classes: 68Q25, 68R10
13	Jacobo Torán	Lower Bounds for Space in Resolution.	CSL	1999	DBLP DOI BibTeX RDF	lower bounds, Resolution, space, complexity measures, pebbling game
13	Andreas Goerdt	Random Regular Graphs with Edge Faults: Expansion through Cores.	ISAAC	1998	DBLP DOI BibTeX RDF
13	Victor Boyko, Marcus Peinado, Ramarathnam Venkatesan	Speeding up Discrete Log and Factoring Based Schemes via Precomputations.	EUROCRYPT	1998	DBLP DOI BibTeX RDF
13	Dimitris Fotakis 0001, Paul G. Spirakis	(poly(log log n), poly(log log n))-Restricted Verifiers are Unlikely to Exist for Languages in NP.	MFCS	1996	DBLP DOI BibTeX RDF
13	Fong-Chih Shao, A. Yavuz Oruç	Efficient Nonblocking Switching Networks for Interprocessor Communications in Multiprocessor Systems.	IEEE Trans. Parallel Distributed Syst.	1995	DBLP DOI BibTeX RDF
13	Phillip G. Bradford, Rudolf Fleischer	Matching Nuts and Bolts Faster.	ISAAC	1995	DBLP DOI BibTeX RDF
13	Stephen Dean Brown, Jonathan Rose, Zvonko G. Vranesic	A detailed router for field-programmable gate arrays.	IEEE Trans. Comput. Aided Des. Integr. Circuits Syst.	1992	DBLP DOI BibTeX RDF
13	Elias Dahlhaus, Marek Karpinski	A Fast Parallel Algorithm for Computing all Maximal Cliques in a Graph and the Related Problems (Extended Abstract).	SWAT	1988	DBLP DOI BibTeX RDF
13	Alasdair Urquhart	Hard examples for resolution.	J. ACM	1987	DBLP DOI BibTeX RDF