Computing (and Life) Is All about Tradeoffs
From MaRDI portal
Publication:2848971
DOI10.1007/978-3-642-40273-9_9zbMath1394.68165MaRDI QIDQ2848971
Publication date: 13 September 2013
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-40273-9_9
68Q25: Analysis of algorithms and problem complexity
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Toward a model for backtracking and dynamic programming
- Worst-case equilibria
- A stronger model of dynamic programming algorithms
- An implicit data structure supporting insertion, deletion, and search in \(O(\log ^ 2\,n)\) time
- Implicit \(B\)-trees: A new data structure for the dictionary problem
- Selection from read-only memory and sorting with minimum data movement
- Bounds on tradeoffs between randomness and communication complexity
- Tighter lower bounds for nearest neighbor search and related problems in the cell probe model
- Partial match retrieval in implicit data structures
- Communication complexity
- Two time-space tradeoffs for element distinctness
- Lower bounds on communication complexity
- Upper bounds for time-space trade-offs in sorting and selection
- A tradeoff between search and update time for the implicit dictionary problem
- Probabilistic algorithm for testing primality
- Selection and sorting with limited storage
- Implicit data structures for fast search and update
- A time-space tradeoff for sorting on non-oblivious machines
- A lower bound for the time to assure interactive consistency
- The space complexity of approximating the frequency moments
- Time bounds for selection
- Time-space tradeoffs for satisfiability
- A tradeoff between search and update in dictionaries
- PRIMES is in P
- The cell probe complexity of succinct data structures
- Optimal algorithms for parallel polynomial evaluation
- A lower bound on the complexity of approximate nearest-neighbor searching on the Hamming cube
- Pebble Games, Proof Complexity, and Time-Space Trade-offs
- Comparison-based time-space lower bounds for selection
- The Hardness of Being Private
- The Design of Approximation Algorithms
- Authenticated Algorithms for Byzantine Agreement
- Fast Parallel Computation of Polynomials Using Few Processors
- Different Modes of Communication
- How bad is selfish routing?
- A time-space tradeoff for language recognition
- Time-space tradeoffs, multiparty communication complexity, and nearest-neighbor problems
- Implicit dictionaries with O(1) modifications per update and fast search
- Inefficiency of Nash Equilibria
- A Time-Space Tradeoff for Element Distinctness
- Reaching Agreement in the Presence of Faults
- A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation
- Implicit Data Structures for the Dictionary Problem
- Privacy and Communication Complexity
- Rounds in Communication Complexity Revisited
- Erratum: A Fast Monte-Carlo Test for Primality
- The relative efficiency of propositional proof systems
- On the Parallel Evaluation of Multivariate Polynomials
- Near-Optimal Time-Space Tradeoff for Element Distinctness
- Efficient Search for Approximate Nearest Neighbor in High Dimensional Spaces
- A trade-off between space and efficiency for routing tables
- Maintaining Stream Statistics over Sliding Windows
- Approximate Privacy
- Towards in-place geometric algorithms and data structures
- Deterministic simulation of non-deterministic turing machines (Detailed Abstract)
- Time-space tradeoffs in resolution
- On the virtue of succinct proofs
- Some trade-off results for polynomial calculus
- Efficient synchronous snapshots
- Differential Privacy
- Algorithmic mechanism design
