Search results for "sublinear"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
67	Ray Maleh, Anna C. Gilbert	Sublinear Recovery of Sparse Wavelet Signals.	DCC	2008	DBLP DOI BibTeX RDF	sublinear recovery, Haar, Reed Muller, wavelets, sketch, sparse
63	Artur Czumaj, S. Muthukrishnan 0001, Ronitt Rubinfeld, Christian Sohler	08341 Executive Summary - Sublinear Algorithms.	Sublinear Algorithms	2008	DBLP BibTeX RDF
63	Artur Czumaj, S. Muthu Muthukrishnan, Ronitt Rubinfeld, Christian Sohler	08341 Abstracts Collection - Sublinear Algorithms.	Sublinear Algorithms	2008	DBLP BibTeX RDF
63	Bernard Chazelle, Ding Liu, Avner Magen	Sublinear Geometric Algorithms.	Sublinear Algorithms	2005	DBLP BibTeX RDF
63	Artur Czumaj, S. Muthu Muthukrishnan, Ronitt Rubinfeld, Christian Sohler	05291 Abstracts Collection -- Sublinear Algorithms.	Sublinear Algorithms	2005	DBLP BibTeX RDF
58	Funda Ergün, S. Muthukrishnan 0001, Süleyman Cenk Sahinalp	Sublinear Methods for Detecting Periodic Trends in Data Streams.	LATIN	2004	DBLP DOI BibTeX RDF
58	Lawrence L. Larmore, Wojciech Rytter	Efficient Sublinear Time Parallel Algorithms for Dynamic Programming and Context-Free Recognition.	STACS	1992	DBLP DOI BibTeX RDF
56	Vaithilingam Jeyakumar, Guoyin Li 0001	Farkas' lemma for separable sublinear inequalities without qualifications.	Optim. Lett.	2009	DBLP DOI BibTeX RDF	Generalized Farkas’ lemma, Separable sublinear inequalities, Robust linear programming, Duality, Optimality conditions
56	Bin Fu, Zhixiang Chen 0001	Sublinear time width-bounded separators and their application to the protein side-chain packing problem.	J. Comb. Optim.	2008	DBLP DOI BibTeX RDF	Width-bounded separator, Random sampling, Sublinear time algorithm
56	Bernard Chazelle, Ding Liu, Avner Magen	Sublinear geometric algorithms.	STOC	2003	DBLP DOI BibTeX RDF	approximate shortest paths, polyhedral intersection, sublinear algorithms
55	Paolo Ferragina, Roberto Grossi	Optimal On-Line Search and Sublinear Time Update in String Matching.	FOCS	1995	DBLP DOI BibTeX RDF	optimal online search, optimal on-line search, sublinear time update, online searching, arbitrary pattern string, indexed text string, arbitrary string, optimal time, occ occurrences, sublinear time per update, computational complexity, pattern matching, string matching, string matching, search problems, word processing, dynamic algorithm, dynamic setting
48	Artur Czumaj, S. Muthu Muthukrishnan, Ronitt Rubinfeld, Christian Sohler (eds.)	Sublinear Algorithms, 17.08. - 22.08.2008	Sublinear Algorithms	2008	DBLP BibTeX RDF
48	Tali Kaufman, Simon Litsyn, Ning Xie 0002	Breaking the ε-Soundness Bound of the Linearity Test over GF(2).	Sublinear Algorithms	2008	DBLP BibTeX RDF
48	Sumit Ganguly	Lower bound for estimating frequency for update data streams.	Sublinear Algorithms	2008	DBLP BibTeX RDF
48	Artur Czumaj, S. Muthu Muthukrishnan, Ronitt Rubinfeld, Christian Sohler (eds.)	Sublinear Algorithms, 17.07. - 22.07.2005	Sublinear Algorithms	2006	DBLP BibTeX RDF
48	Oded Goldreich 0001	Contemplations on Testing Graph Properties.	Sublinear Algorithms	2005	DBLP BibTeX RDF
48	Oded Goldreich 0001, Dana Ron	Approximating Average Parameters of Graphs.	Sublinear Algorithms	2005	DBLP BibTeX RDF
47	Vassil S. Dimitrov, Kimmo U. Järvinen, Michael J. Jacobson Jr., W. F. Chan, Zhun Huang	Provably Sublinear Point Multiplication on Koblitz Curves and Its Hardware Implementation.	IEEE Trans. Computers	2008	DBLP DOI BibTeX RDF
47	Satyen Kale, Yuval Peres, C. Seshadhri 0001	Noise Tolerance of Expanders and Sublinear Expander Reconstruction.	FOCS	2008	DBLP DOI BibTeX RDF
47	Jesper Jansson 0001, Kunihiko Sadakane, Wing-Kin Sung	Compressed Dynamic Tries with Applications to LZ-Compression in Sublinear Time and Space.	FSTTCS	2007	DBLP DOI BibTeX RDF
47	Sudipto Guha, Andrew McGregor 0001, Suresh Venkatasubramanian	Streaming and sublinear approximation of entropy and information distances.	SODA	2006	DBLP DOI BibTeX RDF
47	Tatsuyuki Matsushita, Hideki Imai	A Public-Key Black-Box Traitor Tracing Scheme with Sublinear Ciphertext Size Against Self-Defensive Pirates.	ASIACRYPT	2004	DBLP DOI BibTeX RDF	Public-key traitor tracing, Black-box tracing, Self-defensive pirates
47	Marek Karpinski, Wojciech Rytter	On a Sublinear Time Parallel Construction of Optimal Binary Search Trees.	MFCS	1994	DBLP DOI BibTeX RDF
46	Stefan S. Dantchev, Tom Friedetzky, Lars Nagel 0001	Sublinear-Time Algorithms for Tournament Graphs.	COCOON	2009	DBLP DOI BibTeX RDF	random walk, tournament, sublinear-time algorithms
46	Tugkan Batu, Ravi Kumar 0001, Ronitt Rubinfeld	Sublinear algorithms for testing monotone and unimodal distributions.	STOC	2004	DBLP DOI BibTeX RDF	monotone and unimodal distributions, property testing, distribution testing, sublinear algorithms
46	Tugkan Batu, Funda Ergün, Joe Kilian, Avner Magen, Sofya Raskhodnikova, Ronitt Rubinfeld, Rahul Sami	A sublinear algorithm for weakly approximating edit distance.	STOC	2003	DBLP DOI BibTeX RDF	approximation, string matching, sublinear algorithms
46	Lefteris M. Kirousis, Paul G. Spirakis, Philippas Tsigas	Reading Many Variables in One Atomic Operation: Solutions with Linear or Sublinear Complexity.	IEEE Trans. Parallel Distributed Syst.	1994	DBLP DOI BibTeX RDF	sublinear complexity, deterministic protocol, memory location, Archimedean time assumption, computational complexity, protocols, distributed algorithms, time complexity, probabilistic algorithm, linear complexity, space complexity, atomic operation
43	Alexandr Andoni, Piotr Indyk, Krzysztof Onak, Ronitt Rubinfeld	External Sampling.	ICALP (1)	2009	DBLP DOI BibTeX RDF
42	Sharon Marko, Dana Ron	Approximating the distance to properties in bounded-degree and general sparse graphs.	ACM Trans. Algorithms	2009	DBLP DOI BibTeX RDF	Sublinear approximation algorithms, property testing, graph properties, distance approximation
40	Tugkan Batu, Lance Fortnow, Ronitt Rubinfeld, Warren D. Smith, Patrick White	Testing that distributions are close.	FOCS	2000	DBLP DOI BibTeX RDF	distribution closeness testing, rapidly mixing process, computational complexity, lower bound, probability, probability, sampling, Markov processes, Markov process, sublinear algorithm, sublinear algorithms, sampling methods
40	Paolo Ferragina, Giovanni Manzini	Opportunistic Data Structures with Applications.	FOCS	2000	DBLP DOI BibTeX RDF	opportunistic data structures, data indexing, succinct suffix array, suffix tree data structures, suffix array data structures, Glimpse tool, sublinear query time complexity, sublinear space complexity, computational complexity, data structures, search, data compression, data compression, entropy, database theory, data set, database indexing, query performance
36	Bin Fu, Zhiyu Zhao	Separating Sublinear Time Computations by Approximate Diameter.	COCOA	2008	DBLP DOI BibTeX RDF
36	Michael T. Goodrich, Jonathan Z. Sun	Checking Value-Sensitive Data Structures in Sublinear Space.	ISAAC	2007	DBLP DOI BibTeX RDF
36	Vassil S. Dimitrov, Laurent Imbert, Andrew Zakaluzny	Multiplication by a Constant is Sublinear.	IEEE Symposium on Computer Arithmetic	2007	DBLP DOI BibTeX RDF
36	Sofya Raskhodnikova, Dana Ron, Ronitt Rubinfeld, Adam D. Smith	Sublinear Algorithms for Approximating String Compressibility.	APPROX-RANDOM	2007	DBLP DOI BibTeX RDF
36	Bin Fu, Zhixiang Chen 0001	Sublinear Time Width-Bounded Separators and Their Application to the Protein Side-Chain Packing Problem.	AAIM	2006	DBLP DOI BibTeX RDF
36	Petra Berenbrink, Funda Ergün, Tom Friedetzky	Finding Frequent Patterns in a String in Sublinear Time.	ESA	2005	DBLP DOI BibTeX RDF
36	Zhixiang Chen 0001, Richard H. Fowler, Ada Wai-Chee Fu, Chunyue Wang	Linear and Sublinear Time Algorithms for Mining Frequent Traversal Path Patterns from Very Large Web Logs.	IDEAS	2003	DBLP DOI BibTeX RDF
35	Artur Czumaj, Christian Sohler	Estimating the weight of metric minimum spanning trees in sublinear-time.	STOC	2004	DBLP DOI BibTeX RDF	approximations algorithms, randomized algorithms, minimum spanning tree, sublinear-time algorithms
35	William I. Chang, Eugene L. Lawler	Approximate String Matching in Sublinear Expected Time	FOCS	1990	DBLP DOI BibTeX RDF	random string, infrequent errors, sublinear expected time, pattern string, substring matching, dynamic programming, efficient algorithms, genetics, insertions, approximate string matching, deletions, substitutions, differences, molecular biology, text string
35	Andrew V. Goldberg, Serge A. Plotkin, Pravin M. Vaidya	Sublinear-Time Parallel Algorithms for Matching and Related Problems	FOCS	1988	DBLP DOI BibTeX RDF	sublinear-time parallel algorithms, maximal node-disjoint paths, zero-one networks, matching, depth-first search, node-disjoint paths, combinatorial structure
33	Timothy M. Chan, Mihai Patrascu, Liam Roditty	Dynamic Connectivity: Connecting to Networks and Geometry.	FOCS	2008	DBLP DOI BibTeX RDF
33	Bilel Derbel	Local Maps: New Insights into Mobile Agent Algorithms.	DISC	2008	DBLP DOI BibTeX RDF	local maps, Mobile agents, time complexity
33	Vassil S. Dimitrov, Kimmo U. Järvinen, Michael J. Jacobson Jr., W. F. Chan, Zhun Huang	FPGA Implementation of Point Multiplication on Koblitz Curves Using Kleinian Integers.	CHES	2006	DBLP DOI BibTeX RDF
33	Morteza Fayyazi, David R. Kaeli, Waleed Meleis	Parallel Maximum Weight Bipartite Matching Algorithms for Scheduling in Input-Queued Switches.	IPDPS	2004	DBLP DOI BibTeX RDF
31	Sándor P. Fekete, Dietmar Fey, Marcus Komann, Alexander Kröller, Marc Reichenbach, Christiane Schmidt 0001	Distributed vision with smart pixels.	SCG	2009	DBLP DOI BibTeX RDF	distributed vision, sweepline algorithms, distributed algorithms, principle component analysis, sublinear algorithms
31	Joan Feigenbaum, Yuval Ishai, Tal Malkin, Kobbi Nissim, Martin J. Strauss, Rebecca N. Wright	Secure multiparty computation of approximations.	ACM Trans. Algorithms	2006	DBLP DOI BibTeX RDF	distributed data processing, sublinear communication, Privacy
29	Kyohei Chiba, Hiro Ito	Sublinear Computation Paradigm: Constant-Time Algorithms and Sublinear Progressive Algorithms.	IEICE Trans. Fundam. Electron. Commun. Comput. Sci.	2022	DBLP DOI BibTeX RDF
25	Omar U. Florez, Alexander Ocsa, Curtis E. Dyreson	Sublinear querying of realistic timeseries and its application to human motion.	Multimedia Information Retrieval	2010	DBLP DOI BibTeX RDF	scalable indexing, search and structuring, human motion
25	Jakub Pawlewicz, Mihai Patrascu	Order Statistics in the Farey Sequences in Sublinear Time and Counting Primitive Lattice Points in Polygons.	Algorithmica	2009	DBLP DOI BibTeX RDF	Möbius inversion, Mertens function, Primitive lattice points, Farey sequence
25	MoonShik Lee, Daegun Ma, MinJae Seo	Breaking Two k-Resilient Traitor Tracing Schemes with Sublinear Ciphertext Size.	ACNS	2009	DBLP DOI BibTeX RDF	public-key traitor tracing, black-box tracing, self-defensive pirates, linear attack, cryptanalysis
25	Aggelos Kiayias, Serdar Pehlivanoglu	On the security of a public-key traitor tracing scheme with sublinear ciphertext size.	Digital Rights Management Workshop	2009	DBLP DOI BibTeX RDF	blackbox tracing, public key cryptosystem, traitor tracing
25	Bin Fu, Zhixiang Chen 0001	A Sublinear Time Randomized Algorithm for Coset Enumeration in the Black Box Model.	COCOON	2008	DBLP DOI BibTeX RDF
25	Mehmet Akçakaya, Vahid Tarokh	Noisy compressive sampling limits in linear and sublinear regimes.	CISS	2008	DBLP DOI BibTeX RDF
25	Mark A. Iwen, Craig V. Spencer	Improved bounds for a deterministic sublinear-time Sparse Fourier Algorithm.	CISS	2008	DBLP DOI BibTeX RDF
25	Jakub Pawlewicz	Order Statistics in the Farey Sequences in Sublinear Time.	ESA	2007	DBLP DOI BibTeX RDF
25	Mikkel Thorup, Uri Zwick	Spanners and emulators with sublinear distance errors.	SODA	2006	DBLP DOI BibTeX RDF
25	Nicholas D. Pattengale, Bernard M. E. Moret	A Sublinear-Time Randomized Approximation Scheme for the Robinson-Foulds Metric.	RECOMB	2006	DBLP DOI BibTeX RDF
25	Leena Salmela, Jorma Tarhio	Sublinear Algorithms for Parameterized Matching.	CPM	2006	DBLP DOI BibTeX RDF
25	Javier Peña 0001	On the block-structured distance to non-surjectivity of sublinear mappings.	Math. Program.	2005	DBLP DOI BibTeX RDF
25	Mihai Badoiu, Artur Czumaj, Piotr Indyk, Christian Sohler	Facility Location in Sublinear Time.	ICALP	2005	DBLP DOI BibTeX RDF
25	Artur Czumaj, Christian Sohler	Sublinear-Time Approximation for Clustering Via Random Sampling.	ICALP	2004	DBLP DOI BibTeX RDF
25	Bernard Chazelle	Sublinear Computing.	ESA	2003	DBLP DOI BibTeX RDF
25	Kurt Mehlhorn, Ulrich Meyer 0001	External-Memory Breadth-First Search with Sublinear I/O.	ESA	2002	DBLP DOI BibTeX RDF
25	Klaus Wich	Sublinear Ambiguity.	MFCS	2000	DBLP DOI BibTeX RDF
25	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
25	Lefteris M. Kirousis, Paul G. Spirakis, Philippas Tsigas	Reading Many Variables in One Atomic Operation: Solutions With Linear or Sublinear Complexity.	WDAG	1991	DBLP DOI BibTeX RDF
25	Svante Carlsson, Christos Levcopoulos, Ola Petersson	Sublinear Merging and Natural Merge Sort.	SIGAL International Symposium on Algorithms	1990	DBLP DOI BibTeX RDF
22	Hossein Maserrat, Jian Pei	Neighbor query friendly compression of social networks.	KDD	2010	DBLP DOI BibTeX RDF	MPk linearization, social networks, compression
22	Atish Das Sarma, Danupon Nanongkai, Gopal Pandurangan, Prasad Tetali	Efficient distributed random walks with applications.	PODC	2010	DBLP DOI BibTeX RDF	decentralized computation, random spanning tree, distributed algorithms, random walks, random sampling, mixing time
22	Moni Naor, Guy N. Rothblum	The complexity of online memory checking.	J. ACM	2009	DBLP DOI BibTeX RDF	Memory checking, authentication
22	Chandra Chekuri, Sanjeev Khanna	Edge-disjoint paths revisited.	ACM Trans. Algorithms	2007	DBLP DOI BibTeX RDF	multicommodity flow relaxation, approximation algorithm, greedy algorithm, Edge-disjoint paths
22	Lizhong Zheng, David N. C. Tse, Muriel Médard	Channel Coherence in the Low-SNR Regime.	IEEE Trans. Inf. Theory	2007	DBLP DOI BibTeX RDF
22	Ke Liu 0010, Akbar M. Sayeed	Type-Based Decentralized Detection in Wireless Sensor Networks.	IEEE Trans. Signal Process.	2007	DBLP DOI BibTeX RDF
22	Robert Fitch, Zack J. Butler	Scalable Locomotion for Large Self-Reconfiguring Robots.	ICRA	2007	DBLP DOI BibTeX RDF
22	Bernard Chazelle	Ushering in a New Era of Algorithm Design.	ICALP	2007	DBLP DOI BibTeX RDF
22	Artur Czumaj, Christian Sohler	Small Space Representations for Metric Min-Sum k -Clustering and Their Applications.	STACS	2007	DBLP DOI BibTeX RDF
22	János Csirik, David S. Johnson, Claire Kenyon, James B. Orlin, Peter W. Shor, Richard R. Weber	On the Sum-of-Squares algorithm for bin packing.	J. ACM	2006	DBLP DOI BibTeX RDF	Approximation algorithms, bin packing, average case analysis
22	Bilel Derbel, Mohamed Mosbah 0001, Akka Zemmari	Fast distributed graph partition and application.	IPDPS	2006	DBLP DOI BibTeX RDF
22	Srikanta Tirthapura, Sudip Seal, Srinivas Aluru	A Formal Analysis of Space Filling Curves for Parallel Domain Decomposition.	ICPP	2006	DBLP DOI BibTeX RDF	parallel algorithms, probabilistic analysis, domain decomposition, space filling curves
22	Oded Goldreich 0001, Dana Ron	Approximating Average Parameters of Graphs.	APPROX-RANDOM	2006	DBLP DOI BibTeX RDF
22	Mikhail V. Solodov	Convergence rate analysis of iteractive algorithms for solving variational inequality problems.	Math. Program.	2003	DBLP DOI BibTeX RDF
22	Michael Elkin, David Peleg	Approximating k-Spanner Problems for k>2.	IPCO	2001	DBLP DOI BibTeX RDF
22	Ran Canetti, Yuval Ishai, Ravi Kumar 0001, Michael K. Reiter, Ronitt Rubinfeld, Rebecca N. Wright	Selective private function evaluation with applications to private statistics.	PODC	2001	DBLP DOI BibTeX RDF
22	Rahul Santhanam	On Separators, Segregators and Time versus Space.	CCC	2001	DBLP DOI BibTeX RDF
22	Gianfranco Bilardi, Kattamuri Ekanadham, Pratap Pattnaik	Computational power of pipelined memory hierarchies.	SPAA	2001	DBLP DOI BibTeX RDF
22	Ulrich Meyer 0001, Peter Sanders 0001	Parallel Shortest Path for Arbitrary Graphs.	Euro-Par	2000	DBLP DOI BibTeX RDF
22	Lenore Cowen, Christopher G. Wagner	Compact roundtrip routing in directed networks (extended abstract).	PODC	2000	DBLP DOI BibTeX RDF
22	Gonzalo Navarro 0001, Ricardo A. Baeza-Yates	Fast Multi-dimensional Approximate Pattern Matching.	CPM	1999	DBLP DOI BibTeX RDF
22	Rusins Freivalds, Marek Karpinski	Lower Time Bounds for Randomized Computation.	ICALP	1995	DBLP DOI BibTeX RDF
22	Nick D. Dendris, Lefteris M. Kirousis, Yannis C. Stamatiou, Dimitrios M. Thilikos	Partiality and Approximation Schemes for Local Consistency in Networks of Constraints.	FSTTCS	1995	DBLP DOI BibTeX RDF
22	John Turek, Walter Ludwig, Joel L. Wolf, Lisa Fleischer, Prasoon Tiwari, Jason Glasgow, Uwe Schwiegelshohn, Philip S. Yu	Scheduling Parallelizable Tasks to Minimize Average Response Time.	SPAA	1994	DBLP DOI BibTeX RDF
22	Lane A. Hemachandra, Albrecht Hoene	Collapsing Degrees via Strong Computation (Extended Abstract).	ICALP	1991	DBLP DOI BibTeX RDF
22	V. Nageshwara Rao, Vipin Kumar 0001	Superlinear Speedup in Parallel State-Space Search.	FSTTCS	1988	DBLP DOI BibTeX RDF
20	Swastik Kopparty, Shubhangi Saraf	Local list-decoding and testing of random linear codes from high error.	STOC	2010	DBLP DOI BibTeX RDF	dual-BCH codes, noisy parity, random codes, property testing, list-decoding, sublinear-time algorithms
20	Anna C. Gilbert, Yi Li 0002, Ely Porat, Martin J. Strauss	Approximate sparse recovery: optimizing time and measurements.	STOC	2010	DBLP DOI BibTeX RDF	approximation, embedding, sketching, sublinear algorithms, sparse approximation
20	Nir Ailon, Bernard Chazelle, Seshadhri Comandur, Ding Liu	Property-Preserving Data Reconstruction.	Algorithmica	2008	DBLP DOI BibTeX RDF	Monotonicity testing, Sublinear algorithms
20	Tali Kaufman, Madhu Sudan 0001	Algebraic property testing: the role of invariance.	STOC	2008	DBLP DOI BibTeX RDF	error-correcting codes, locally testable codes, sublinear time algorithms
20	Irit Dinur, Elena Grigorescu, Swastik Kopparty, Madhu Sudan 0001	Decodability of group homomorphisms beyond the johnson bound.	STOC	2008	DBLP DOI BibTeX RDF	hadamard codes, list decoding, sublinear time algorithms
20	Elena Grigorescu, Tali Kaufman, Madhu Sudan 0001	2-Transitivity Is Insufficient for Local Testability.	CCC	2008	DBLP DOI BibTeX RDF	error correcting codes, property testing, sublinear time algorithms