Computing (and Life) Is All about Tradeoffs

DOI10.1007/978-3-642-40273-9_9zbMATH Open1394.68165OpenAlexW2188557740MaRDI QIDQ2848971FDOQ2848971

Allan Borodin

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

Recommendations

• Time-memory-processor trade-offs
• A simple empirical formula for categorizing computing operations
• The duality of computation
• Limits of computation. From a programming perspective
• scientific article; zbMATH DE number 1042857
• A very personal reminiscence on the problem of computational complexity
• Non-recursive trade-offs are ``almost everywhere
• On the efficiency and capacity of computers

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cites Work

• Differential Privacy
• The space complexity of approximating the frequency moments
• The Design of Approximation Algorithms
• Worst-case equilibria
• How bad is selfish routing?
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Probabilistic algorithm for testing primality
• PRIMES is in P
• Inefficiency of Nash Equilibria
• The relative efficiency of propositional proof systems
• Algorithmic mechanism design
• Fast Parallel Computation of Polynomials Using Few Processors
• Authenticated Algorithms for Byzantine Agreement
• Reaching Agreement in the Presence of Faults
• Rounds in Communication Complexity Revisited
• Maintaining Stream Statistics over Sliding Windows
• Time bounds for selection
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the Parallel Evaluation of Multivariate Polynomials
• Title not available (Why is that?)
• Communication complexity
• Lower bounds on communication complexity
• The Hardness of Being Private
• Privacy and Communication Complexity
• Selection and sorting with limited storage
• Time-space tradeoffs for satisfiability
• A lower bound for the time to assure interactive consistency
• Upper bounds for time-space trade-offs in sorting and selection
• Comparison-based time-space lower bounds for selection
• Towards in-place geometric algorithms and data structures
• Selection from read-only memory and sorting with minimum data movement
• Title not available (Why is that?)
• An implicit data structure supporting insertion, deletion, and search in \(O(\log ^ 2\,n)\) time
• Title not available (Why is that?)
• Implicit dictionaries with O(1) modifications per update and fast search
• Toward a model for backtracking and dynamic programming
• A stronger model of dynamic programming algorithms
• The cell probe complexity of succinct data structures
• A trade-off between space and efficiency for routing tables
• Efficient Search for Approximate Nearest Neighbor in High Dimensional Spaces
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Implicit data structures for fast search and update
• Optimal algorithms for parallel polynomial evaluation
• Title not available (Why is that?)
• Implicit Data Structures for the Dictionary Problem
• A tradeoff between search and update time for the implicit dictionary problem
• A tradeoff between search and update in dictionaries
• A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation
• Implicit \(B\)-trees: A new data structure for the dictionary problem
• Erratum: A Fast Monte-Carlo Test for Primality
• Bounds on tradeoffs between randomness and communication complexity
• A lower bound on the complexity of approximate nearest-neighbor searching on the Hamming cube
• Title not available (Why is that?)
• Tighter lower bounds for nearest neighbor search and related problems in the cell probe model
• Partial match retrieval in implicit data structures
• A time-space tradeoff for language recognition
• A time-space tradeoff for sorting on non-oblivious machines
• Time-space tradeoffs, multiparty communication complexity, and nearest-neighbor problems
• Two time-space tradeoffs for element distinctness
• A Time-Space Tradeoff for Element Distinctness
• Near-Optimal Time-Space Tradeoff for Element Distinctness
• Deterministic simulation of non-deterministic turing machines (Detailed Abstract)
• Different Modes of Communication
• Pebble games, proof complexity, and time-space trade-offs
• Some trade-off results for polynomial calculus
• Time-space tradeoffs in resolution
• On the virtue of succinct proofs
• Approximate Privacy
• Efficient synchronous snapshots

Uses Software

• PrivateLR

This page was built for publication: Computing (and Life) Is All about Tradeoffs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2848971)