Search results for "cell-probe"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
112	Yitong Yin	Cell-Probe Proofs and Nondeterministic Cell-Probe Complexity.	ICALP (1)	2008	DBLP DOI BibTeX RDF
66	Mihai Patrascu, Erik D. Demaine	Lower bounds for dynamic connectivity.	STOC	2004	DBLP DOI BibTeX RDF	cell-probe complexity, dynamic connectivity, dynamic graph problems, lower bounds for data structures, partial sums problem
61	Monika Rauch Henzinger, Michael L. Fredman	Lower Bounds for Fully Dynamic Connectivity Problems in Graphs.	Algorithmica	1998	DBLP DOI BibTeX RDF	Dynamic planarity testing, Dynamic connectivity testing, Dynamic planarity testing, Dynamic connectivity testing, Lower bounds, Lower bounds, Key words, Cell probe model, Cell probe model
48	Amit Chakrabarti, Oded Regev 0001	An Optimal Randomised Cell Probe Lower Bound for Approximate Nearest Neighbour Searching.	FOCS	2004	DBLP DOI BibTeX RDF
48	Pranab Sen, Srinivasan Venkatesh 0001	Lower Bounds in the Quantum Cell Probe Model.	ICALP	2001	DBLP DOI BibTeX RDF
46	Mihai Patrascu	Lower bounds for 2-dimensional range counting.	STOC	2007	DBLP DOI BibTeX RDF	cell-probe complexity, orthogonal range queries, lower bounds
46	Amir M. Ben-Amram, Zvi Galil	Lower Bounds for Dynamic Data Structures on Algebraic RAMs.	Algorithmica	2002	DBLP DOI BibTeX RDF	Cell-probe lower bounds, Dynamic prefix sum, Union-find, Random access machine
46	Daniel J. Rosenkrantz, Lin Yu, S. S. Ravi	Efficient Construction of Minimum Makespan Schedules for Tasks with a Fixed Number of Distinct Execution Times.	Algorithmica	2001	DBLP DOI BibTeX RDF	Cell-probe lower bounds, Dynamic prefix sum, Union-find, Random access machine
46	James Aspnes, David Eisenstat, Yitong Yin	Low-contention data structures.	SPAA	2010	DBLP DOI BibTeX RDF	data structure, memory contention, cell-probe model
41	Rasmus Pagh	On the cell probe complexity of membership and perfect hashing.	STOC	2001	DBLP DOI BibTeX RDF
41	T. S. Jayram, Subhash Khot, Ravi Kumar 0001, Yuval Rabani	Cell-probe lower bounds for the partial match problem.	STOC	2003	DBLP DOI BibTeX RDF
37	Alexander Golynski	Cell probe lower bounds for succinct data structures.	SODA	2009	DBLP DOI BibTeX RDF
35	Mihai Patrascu, Mikkel Thorup	Time-space trade-offs for predecessor search.	STOC	2006	DBLP DOI BibTeX RDF	cell-probe complexity, predecessor search, lower bounds
27	Anna Gál, Peter Bro Miltersen	The Cell Probe Complexity of Succinct Data Structures.	ICALP	2003	DBLP DOI BibTeX RDF
27	Pranab Sen	Lower bounds for predecessor searching in the cell probe model.	CCC	2003	DBLP DOI BibTeX RDF
25	Christian Sommer 0001, Elad Verbin, Wei Yu 0007	Distance Oracles for Sparse Graphs.	FOCS	2009	DBLP DOI BibTeX RDF	distance oracle, lopsided set disjointness, data structures, lower bounds, cell-probe model
25	Emanuele Viola	Bit-probe lower bounds for succinct data structures.	STOC	2009	DBLP DOI BibTeX RDF	bit-probe, cell-probe, logarithmic form, ternary value, lower bound, dictionary, succinct data structure, membership query
25	Rajamani Sundar	A Lower Bound for the Dictionary Problem under a Hashing Model	FOCS	1991	DBLP DOI BibTeX RDF	randomized complexities, update costs, deterministic complexities, constant amortized time, multilevel hashing model, log-algorithmic amortized time, nontrivial lower bound, limited wordsize, memory locations, data structures, polynomial space, dictionary problem, cell probe model
21	Yevgeniy Dodis, Sanjeev Khanna	Space Time Tradeoffs for Graph Properties.	ICALP	1999	DBLP DOI BibTeX RDF
17	Rina Panigrahy, Kunal Talwar, Udi Wieder	A Geometric Approach to Lower Bounds for Approximate Near-Neighbor Search and Partial Match.	FOCS	2008	DBLP DOI BibTeX RDF
17	Sankardeep Chakraborty, Christian Engels, Seungbum Jo, Mingmou Liu	Cell-Probe Lower Bound for Accessible Interval Graphs.	CoRR	2023	DBLP DOI BibTeX RDF
17	Tianxiao Li, Jingxun Liang, Huacheng Yu, Renfei Zhou	Tight Cell-Probe Lower Bounds for Dynamic Succinct Dictionaries.	CoRR	2023	DBLP DOI BibTeX RDF
17	Kasper Green Larsen, Rasmus Pagh, Toniann Pitassi, Or Zamir	Optimal Non-Adaptive Cell Probe Dictionaries and Hashing.	CoRR	2023	DBLP DOI BibTeX RDF
17	Tianxiao Li, Jingxun Liang, Huacheng Yu, Renfei Zhou	Tight Cell-Probe Lower Bounds for Dynamic Succinct Dictionaries.	FOCS	2023	DBLP DOI BibTeX RDF
17	Emanuele Viola	Lower bounds for samplers and data structures via the cell-probe separator.	Electron. Colloquium Comput. Complex.	2021	DBLP BibTeX RDF
17	Kasper Green Larsen, Jonathan Lindegaard Starup, Jesper Steensgaard	Further Unifying the Landscape of Cell Probe Lower Bounds.	SOSA	2021	DBLP DOI BibTeX RDF
17	Chi-Hua Chen	A Cell Probe-Based Method for Vehicle Speed Estimation.	IEICE Trans. Fundam. Electron. Commun. Comput. Sci.	2020	DBLP BibTeX RDF
17	Kasper Green Larsen, Jonathan Lindegaard Starup, Jesper Steensgaard	Further Unifying the Landscape of Cell Probe Lower Bounds.	CoRR	2020	DBLP BibTeX RDF
17	Sarvar Patel, Giuseppe Persiano, Kevin Yeo	Lower Bounds for Encrypted Multi-Maps and Searchable Encryption in the Leakage Cell Probe Model.	CRYPTO (1)	2020	DBLP DOI BibTeX RDF
17	Sayan Bhattacharya, Monika Henzinger, Stefan Neumann 0003	New amortized cell-probe lower bounds for dynamic problems.	Theor. Comput. Sci.	2019	DBLP DOI BibTeX RDF
17	Sayan Bhattacharya, Monika Henzinger, Stefan Neumann 0003	New Amortized Cell-Probe Lower Bounds for Dynamic Problems.	CoRR	2019	DBLP BibTeX RDF
17	Sarvar Patel, Giuseppe Persiano, Kevin Yeo	Leakage Cell Probe Model: Lower Bounds for Key-Equality Mitigation in Encrypted Multi-Maps.	IACR Cryptol. ePrint Arch.	2019	DBLP BibTeX RDF
17	Josh Alman, Joshua R. Wang, Huacheng Yu	Cell-probe lower bounds from online communication complexity.	STOC	2018	DBLP DOI BibTeX RDF
17	Diptarka Chakraborty, Lior Kamma, Kasper Green Larsen	Tight cell probe bounds for succinct Boolean matrix-vector multiplication.	STOC	2018	DBLP DOI BibTeX RDF
17	Josh Alman, Joshua R. Wang, Huacheng Yu	Cell-Probe Lower Bounds from Online Communication Complexity.	Electron. Colloquium Comput. Complex.	2017	DBLP BibTeX RDF
17	Diptarka Chakraborty, Lior Kamma, Kasper Green Larsen	Tight Cell Probe Bounds for Succinct Boolean Matrix-Vector Multiplication.	CoRR	2017	DBLP BibTeX RDF
17	Josh Alman, Joshua R. Wang, Huacheng Yu	Cell-Probe Lower Bounds from Online Communication Complexity.	CoRR	2017	DBLP BibTeX RDF
17	Omri Weinstein, Huacheng Yu	Amortized Dynamic Cell-Probe Lower Bounds from Four-Party Communication.	Electron. Colloquium Comput. Complex.	2016	DBLP BibTeX RDF
17	Omri Weinstein, Huacheng Yu	Amortized Dynamic Cell-Probe Lower Bounds from Four-Party Communication.	CoRR	2016	DBLP BibTeX RDF
17	Omri Weinstein, Huacheng Yu	Amortized Dynamic Cell-Probe Lower Bounds from Four-Party Communication.	FOCS	2016	DBLP DOI BibTeX RDF
17	Raphaël Clifford, Markus Jalsenius, Benjamin Sach	Cell-Probe Lower Bounds for Bit Stream Computation.	ESA	2016	DBLP DOI BibTeX RDF
17	Huacheng Yu	Cell-probe lower bounds for dynamic problems via a new communication model.	STOC	2016	DBLP DOI BibTeX RDF
17	Huacheng Yu	Cell-probe Lower Bounds for Dynamic Problems via a New Communication Model.	CoRR	2015	DBLP BibTeX RDF
17	Raphaël Clifford, Markus Jalsenius, Benjamin Sach	Cell-probe bounds for online edit distance and other pattern matching problems.	SODA	2015	DBLP DOI BibTeX RDF
17	Raphaël Clifford, Markus Jalsenius, Benjamin Sach	Cell-Probe Bounds for Online Edit Distance and Other Pattern Matching Problems.	CoRR	2014	DBLP BibTeX RDF
17	Raphaël Clifford, Markus Jalsenius, Benjamin Sach	Tight Cell-Probe Bounds for Online Hamming Distance Computation.	SODA	2013	DBLP DOI BibTeX RDF
17	Raphaël Clifford, Markus Jalsenius, Benjamin Sach	Tight Cell-Probe Bounds for Online Hamming Distance Computation	CoRR	2012	DBLP BibTeX RDF
17	Kasper Green Larsen	Higher Cell Probe Lower Bounds for Evaluating Polynomials.	FOCS	2012	DBLP DOI BibTeX RDF
17	Kasper Green Larsen	The cell probe complexity of dynamic range counting.	STOC	2012	DBLP DOI BibTeX RDF
17	Raphaël Clifford, Markus Jalsenius	Lower Bounds for Online Integer Multiplication and Convolution in the Cell-Probe Model	CoRR	2011	DBLP BibTeX RDF
17	Kasper Green Larsen	The Cell Probe Complexity of Dynamic Range Counting	CoRR	2011	DBLP BibTeX RDF
17	Mihai Patrascu	Unifying the Landscape of Cell-Probe Lower Bounds.	SIAM J. Comput.	2011	DBLP DOI BibTeX RDF
17	Allan Grønlund Jørgensen, Kasper Green Larsen	Range Selection and Median: Tight Cell Probe Lower Bounds and Adaptive Data Structures.	SODA	2011	DBLP DOI BibTeX RDF
17	Raphaël Clifford, Markus Jalsenius	Lower Bounds for Online Integer Multiplication and Convolution in the Cell-Probe Model.	ICALP (1)	2011	DBLP DOI BibTeX RDF
17	Mihai Patrascu	Unifying the Landscape of Cell-Probe Lower Bounds	CoRR	2010	DBLP BibTeX RDF
17	Yitong Yin	Cell-Probe Proofs.	ACM Trans. Comput. Theory	2010	DBLP DOI BibTeX RDF
17	Amit Chakrabarti, Oded Regev 0001	An Optimal Randomized Cell Probe Lower Bound for Approximate Nearest Neighbor Searching.	SIAM J. Comput.	2010	DBLP DOI BibTeX RDF
17	Shen Dong, Xiao Qin 0001, Yi Zhang, Qixin Shi, Bin Ran	Dynamic network flow modeling based on cell probe data.	Intelligent Vehicles Symposium	2010	DBLP DOI BibTeX RDF
17	Mihai Patrascu, Emanuele Viola	Cell-Probe Lower Bounds for Succinct Partial Sums.	SODA	2010	DBLP DOI BibTeX RDF
17	Ke Yi 0001, Qin Zhang 0001	On the Cell Probe Complexity of Dynamic Membership.	SODA	2010	DBLP DOI BibTeX RDF
17	Mark Greve, Allan Grønlund Jørgensen, Kasper Dalgaard Larsen, Jakob Truelsen	Cell Probe Lower Bounds and Approximations for Range Mode.	ICALP (1)	2010	DBLP DOI BibTeX RDF
17	Emanuele Viola	Cell-Probe Lower Bounds for Prefix Sums.	Electron. Colloquium Comput. Complex.	2009	DBLP BibTeX RDF
17	Emanuele Viola	Cell-Probe Lower Bounds for Prefix Sums	CoRR	2009	DBLP BibTeX RDF
17	Pranab Sen, Srinivasan Venkatesh 0001	Lower bounds for predecessor searching in the cell probe model.	J. Comput. Syst. Sci.	2008	DBLP DOI BibTeX RDF
17	Anna Gál, Peter Bro Miltersen	The cell probe complexity of succinct data structures.	Theor. Comput. Sci.	2007	DBLP DOI BibTeX RDF
17	Mihai Patrascu, Erik D. Demaine	Logarithmic Lower Bounds in the Cell-Probe Model.	SIAM J. Comput.	2006	DBLP DOI BibTeX RDF
17	Anna Gál, Peter Bro Miltersen	The Cell Probe Complexity of Succinct Data Structures.	Complexity of Boolean Functions	2006	DBLP BibTeX RDF
17	Mihai Patrascu, Erik D. Demaine	Logarithmic Lower Bounds in the Cell-Probe Model	CoRR	2005	DBLP BibTeX RDF
17	T. S. Jayram, Subhash Khot, Ravi Kumar 0001, Yuval Rabani	Cell-probe lower bounds for the partial match problem.	J. Comput. Syst. Sci.	2004	DBLP DOI BibTeX RDF
17	Amit Chakrabarti, Oded Regev 0001	An Optimal Randomised Cell Probe Lower Bound for Approximate Nearest Neighbour Searching	Electron. Colloquium Comput. Complex.	2003	DBLP BibTeX RDF
17	Pranab Sen, Srinivasan Venkatesh 0001	Lower bounds for predecessor searching in the cell probe model	CoRR	2003	DBLP BibTeX RDF
17	Omer Barkol, Yuval Rabani	Tighter Lower Bounds for Nearest Neighbor Search and Related Problems in the Cell Probe Model.	J. Comput. Syst. Sci.	2002	DBLP DOI BibTeX RDF
17	Pranab Sen, Srinivasan Venkatesh 0001	Lower bounds in the quantum cell probe model	CoRR	2001	DBLP BibTeX RDF
17	Stephen Alstrup, Thore Husfeldt, Theis Rauhe	A cell probe lower bound for dynamic nearest-neighbor searching.	SODA	2001	DBLP BibTeX RDF
17	Omer Barkol, Yuval Rabani	Tighter bounds for nearest neighbor search and related problems in the cell probe model.	STOC	2000	DBLP DOI BibTeX RDF
17	Peter Bro Miltersen	On the Cell Probe Complexity of Polynomial Evaluation.	Theor. Comput. Sci.	1995	DBLP DOI BibTeX RDF
17	Michael L. Fredman, Michael E. Saks	The Cell Probe Complexity of Dynamic Data Structures	STOC	1989	DBLP DOI BibTeX RDF
14	Thore Husfeldt, Theis Rauhe, Søren Skyum	Lower Bounds for Dynamic Transitive Closure, Planar Point Location, and Parentheses Matching.	SWAT	1996	DBLP DOI BibTeX RDF
10	Rajendra Shinde, Ashish Goel, Pankaj Gupta 0002, Debojyoti Dutta	Similarity search and locality sensitive hashing using ternary content addressable memories.	SIGMOD Conference	2010	DBLP DOI BibTeX RDF	tcam, similarity search, nearest neighbor search, locality sensitive hashing
10	Boaz Patt-Shamir, Allon Shafrir	Approximate distributed top- k queries.	Distributed Comput.	2008	DBLP DOI BibTeX RDF	Sensor networks, Distributed algorithms, Communication complexity, Random sampling, Aggregate queries
10	Alexandr Andoni, Dorian Croitoru, Mihai Patrascu	Hardness of Nearest Neighbor under L-infinity.	FOCS	2008	DBLP DOI BibTeX RDF
10	Arash Farzan, J. Ian Munro	Succinct Representations of Arbitrary Graphs.	ESA	2008	DBLP DOI BibTeX RDF
10	Rajeev Raman, Venkatesh Raman 0001, Srinivasa Rao Satti	Succinct indexable dictionaries with applications to encoding k-ary trees, prefix sums and multisets.	ACM Trans. Algorithms	2007	DBLP DOI BibTeX RDF	Dictionaries, sets, perfect hashing, multisets, prefix sums, tries, succinct data structures
10	Philip Bille, Anna Pagh, Rasmus Pagh	Fast Evaluation of Union-Intersection Expressions.	ISAAC	2007	DBLP DOI BibTeX RDF
10	Mihai Patrascu, Mikkel Thorup	Randomization does not help searching predecessors.	SODA	2007	DBLP BibTeX RDF
10	Erik D. Demaine, Mihai Patrascu	Tight bounds for dynamic convex hull queries (again).	SCG	2007	DBLP DOI BibTeX RDF	bounded precision, dynamic convex hull, word RAM
10	Micah Adler, Nicholas J. A. Harvey, Kamal Jain, Robert D. Kleinberg, April Rasala Lehman	On the capacity of information networks.	SODA	2006	DBLP DOI BibTeX RDF
10	Mihai Patrascu, Mikkel Thorup	Higher Lower Bounds for Near-Neighbor and Further Rich Problems.	FOCS	2006	DBLP DOI BibTeX RDF
10	Boaz Patt-Shamir, Allon Shafrir	Approximate Top-k Queries in Sensor Networks.	SIROCCO	2006	DBLP DOI BibTeX RDF
10	Christian Worm Mortensen, Seth Pettie	The Complexity of Implicit and Space Efficient Priority Queues.	WADS	2005	DBLP DOI BibTeX RDF
10	Rahul Jain 0001, Jaikumar Radhakrishnan, Pranab Sen	Prior Entanglement, Message Compression and Privacy in Quantum Communication.	CCC	2005	DBLP DOI BibTeX RDF
10	Mihai Patrascu, Erik D. Demaine	Tight bounds for the partial-sums problem.	SODA	2004	DBLP BibTeX RDF
10	Rajeev Raman, Venkatesh Raman 0001, S. Srinivasa Rao 0001	Succinct indexable dictionaries with applications to encoding k-ary trees and multisets.	SODA	2002	DBLP BibTeX RDF
10	Haim Kaplan, Nira Shafrir, Robert Endre Tarjan	Meldable heaps and boolean union-find.	STOC	2002	DBLP DOI BibTeX RDF
10	Paul Beame, Erik Vee	Time-space tradeoffs, multiparty communication complexity, and nearest-neighbor problems.	STOC	2002	DBLP DOI BibTeX RDF
10	Paul Beame, Erik Vee	Time-Space Tradeoffs, Multiparty Communication Complexity, and Nearest-Neighbor Problems.	CCC	2002	DBLP DOI BibTeX RDF
10	Pavol Hell, Ron Shamir, Roded Sharan	A Fully Dynamic Algorithm for Recognizing and Representing Proper Interval Graphs.	ESA	1999	DBLP DOI BibTeX RDF
10	Bernard Chazelle	Geometric Searching over the Rationals.	ESA	1999	DBLP DOI BibTeX RDF
10	Stephen Alstrup, Thore Husfeldt, Theis Rauhe	Marked Ancestor Problems.	FOCS	1998	DBLP DOI BibTeX RDF
10	Thore Husfeldt, Theis Rauhe	Hardness Results for Dynamic Problems by Extensions of Fredman and Saks' Chronogram Method.	ICALP	1998	DBLP DOI BibTeX RDF