Allan Borodin

According to our database1, Allan Borodin authored at least 112 papers between 1969 and 2019.

Collaborative distances:
  • Dijkstra number2 of three.
  • Erdős number3 of two.

Awards

ACM Fellow

ACM Fellow 2014, "For contributions to theoretical computer science in complexity, on-line algorithms, resource tradeoffs, and models of algorithmic paradigms.".

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

2019
On extensions of the deterministic online model for bipartite matching and max-sat.
Theor. Comput. Sci., 2019

Efficient Allocation of Free Stuff.
Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems, 2019

2018
Advice Complexity of Priority Algorithms.
Proceedings of the Approximation and Online Algorithms - 16th International Workshop, 2018

A Simple PTAS for the Dual Bin Packing Problem and Advice Complexity of Its Online Version.
Proceedings of the 1st Symposium on Simplicity in Algorithms, 2018

Big City vs. the Great Outdoors: Voter Distribution and How It Affects Gerrymandering.
Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, 2018

Seasonal Goods and Spoiled Milk: Pricing for a Limited Shelf-Life.
Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems, 2018

Greedy Bipartite Matching in Random Type Poisson Arrival Model.
Proceedings of the Approximation, 2018

2017
Max-Sum Diversification, Monotone Submodular Functions, and Dynamic Updates.
ACM Trans. Algorithms, 2017

Equilibria of Greedy Combinatorial Auctions.
SIAM J. Comput., 2017

On Conceptually Simple Algorithms for Variants of Online Bipartite Matching.
Proceedings of the Approximation and Online Algorithms - 15th International Workshop, 2017

2016
Budgetary Effects on Pricing Equilibrium in Online Markets.
Proceedings of the 2016 International Conference on Autonomous Agents & Multiagent Systems, 2016

2015
Sequential Posted Price Mechanisms with Correlated Valuations.
Proceedings of the Web and Internet Economics - 11th International Conference, 2015

2014
Bounds on Double-Sided Myopic Algorithms for Unconstrained Non-monotoneSubmodular Maximization.
Proceedings of the Algorithms and Computation - 25th International Symposium, 2014

2013
Strategyproof mechanisms for competitive influence in networks.
Proceedings of the 22nd International World Wide Web Conference, 2013

Computing (and Life) Is All about Tradeoffs - A Small Sample of Some Computational Tradeoffs.
Proceedings of the Space-Efficient Data Structures, 2013

2012
On sum coloring and sum multi-coloring for restricted families of graphs.
Theor. Comput. Sci., 2012

Max-Sum diversification, monotone submodular functions and dynamic updates.
Proceedings of the 31st ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2012

2011
How well can primal-dual and local-ratio algorithms perform?
ACM Trans. Algorithms, 2011

Special Issue In Memory of Misha Alekhnovich. Foreword.
Computational Complexity, 2011

2010
Priority algorithms for graph optimization problems.
Theor. Comput. Sci., 2010

Randomized priority algorithms.
Theor. Comput. Sci., 2010

Threshold Models for Competitive Influence in Social Networks.
Proceedings of the Internet and Network Economics - 6th International Workshop, 2010

Price of Anarchy for Greedy Auctions.
Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

On the Relative Merits of Simple Local Search Methods for the MAX-SAT Problem.
Proceedings of the Theory and Applications of Satisfiability Testing, 2010

On the Limitations of Greedy Mechanism Design for Truthful Combinatorial Auctions.
Proceedings of the Automata, Languages and Programming, 37th International Colloquium, 2010

2009
Criteria for Cluster-Based Personalized Search.
Internet Mathematics, 2009

Toward a Model for Backtracking and Dynamic Programming.
Electronic Colloquium on Computational Complexity (ECCC), 2009

Cluster Based Personalized Search.
Proceedings of the Algorithms and Models for the Web-Graph, 6th International Workshop, 2009

Elimination Graphs.
Proceedings of the Automata, Languages and Programming, 36th International Colloquium, 2009

Invited Talk II The Power and Limitations of Simple Algorithms: A Partial Case Study of Greedy Mechanisim Design for Combinatorial Actions.
Proceedings of the Algorithmic Aspects of Wireless Sensor Networks, 2009

2008
Extracting and ranking viral communities using seeds and content similarity.
Proceedings of the HYPERTEXT 2008, 2008

2007
Priority Algorithms for the Subset-Sum Problem.
Proceedings of the Computing and Combinatorics, 13th Annual International Conference, 2007

2006
Further Reflections on a Theory for Basic Algorithms.
Proceedings of the Algorithmic Aspects in Information and Management, 2006

2005
Link analysis ranking: algorithms, theory, and experiments.
ACM Trans. Internet Techn., 2005

Towards a Theory of Algorithms.
Proceedings of the Algorithms and Data Structures, 9th International Workshop, 2005

How Well Can Primal-Dual and Local-Ratio Algorithms Perform?.
Proceedings of the Automata, Languages and Programming, 32nd International Colloquium, 2005

Toward a Model for Backtracking and Dynamic Programming.
Proceedings of the 20th Annual IEEE Conference on Computational Complexity (CCC 2005), 2005

2004
The Power of Priority Algorithms for Facility Location and Set Cover.
Algorithmica, 2004

Priority Algorithms for Graph Optimization Problems.
Proceedings of the Approximation and Online Algorithms, Second International Workshop, 2004

2003
Can We Learn to Beat the Best Stock.
Proceedings of the Advances in Neural Information Processing Systems 16 [Neural Information Processing Systems, 2003

Perturbation of the Hyper-Linked Environment.
Proceedings of the Computing and Combinatorics, 9th Annual International Conference, 2003

2002
(Incremental) priority algorithms.
Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002

On the Power of Priority Algorithms for Facility Location and Set Cover.
Proceedings of the Approximation Algorithms for Combinatorial Optimization, 2002

2001
Adversarial queuing theory.
J. ACM, 2001

Finding authorities and hubs from link structures on the World Wide Web.
Proceedings of the Tenth International World Wide Web Conference, 2001

Stability preserving transformations: packet routing networks with edge capacities and speeds.
Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 2001

2000
On the Competitive Theory and Practice of Portfolio Selection (Extended Abstract).
Proceedings of the LATIN 2000: Theoretical Informatics, 2000

1999
A Time-Space Tradeoff for Undirected Graph Traversal by Walking Automata.
SIAM J. Comput., 1999

On Randomization in On-Line Computation.
Inf. Comput., 1999

Subquadratic Approximation Algorithms for Clustering Problems in High Dimensional Spaces.
Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

Lower Bounds for High Dimensional Nearest Neighbor Search and Related Problems.
Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

1998
Online computation and competitive analysis.
Cambridge University Press, ISBN: 978-0-521-56392-5, 1998

1997
Deterministic Many-to-Many Hot Potato Routing.
IEEE Trans. Parallel Distrib. Syst., 1997

Tribute to Roman Smolensky.
Computational Complexity, 1997

On Ranomization in Online Computation.
Proceedings of the Twelfth Annual IEEE Conference on Computational Complexity, 1997

1996
Time-Space Tradeoffs for Undirected Graph Traversal by Graph Automata.
Inf. Comput., 1996

Adversarial Queueing Theory.
Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, 1996

1995
Competitive Paging with Locality of Reference.
J. Comput. Syst. Sci., 1995

1994
On the Power of Randomization in On-Line Algorithms.
Algorithmica, 1994

A New Measure for the Study of On-Line Algorithms.
Algorithmica, 1994

1993
On Lower Bounds for Read-K-Times Branching Programs.
Computational Complexity, 1993

Towards a Better Understanding of the Pure Packet Routing.
Proceedings of the Algorithms and Data Structures, Third Workshop, 1993

How much can hardware help routing?
Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, 1993

Time Space Tradeoffs (Getting Closer to the Barrier?).
Proceedings of the Algorithms and Computation, 4th International Symposium, 1993

1992
Lower Bounds on the Length of Universal Traversal Sequences.
J. Comput. Syst. Sci., 1992

An Optimal On-Line Algorithm for Metrical Task System.
J. ACM, 1992

Can competitive analysis be made competitive?
Proceedings of the 1992 Conference of the Centre for Advanced Studies on Collaborative Research, 1992

1991
On the Decidability of Sparse Univariate Polynomial Interpolation.
Computational Complexity, 1991

Competitive Paging with Locality of Reference (Preliminary Version)
Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, 1991

Competitive Paging with Locality of Reference (Brief Summary).
Proceedings of the On-Line Algorithms, 1991

1990
On the Decidability of Sparse Univariate Polynomial Interpolation (Preliminary Version)
Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, 1990

On the Power of Randomization in Online Algorithms (Extended Abstract)
Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, 1990

Time-Space Tradeoffs for Undirected Graph Traversal
Proceedings of the 31st Annual Symposium on Foundations of Computer Science, 1990

1989
Distributed FIFO Allocation of Identical Resources Using Small Shared Space.
ACM Trans. Program. Lang. Syst., 1989

Erratum: Two Applications of Inductive Counting for Complementation Problems.
SIAM J. Comput., 1989

Two Applications of Inductive Counting for Complementation Problems.
SIAM J. Comput., 1989

Bounds on Universal Sequences.
SIAM J. Comput., 1989

Lower Bounds on the Length of Universal Traversal Sequences (Detailed Abstract)
Proceedings of the 21st Annual ACM Symposium on Theory of Computing, 1989

1988
Two applications of complementation via inductive counting.
Proceedings of the Proceedings: Third Annual Structure in Complexity Theory Conference, 1988

Juris Hartmanis: building a department-building a discipline.
Proceedings of the Proceedings: Third Annual Structure in Complexity Theory Conference, 1988

1987
An Optimal Online Algorithm for Metrical Task Systems
Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987

1986
Bounds for Width Two Branching Programs.
SIAM J. Comput., 1986

A Time-Space Tradeoff for Element Distinctness.
Proceedings of the STACS 86, 1986

A Tradeoff Between Search and Update Time for the Implicit Dictionary Problem.
Proceedings of the Automata, Languages and Programming, 13th International Colloquium, 1986

1985
Decreasing the Nesting Depth of Expressions Involving Square Roots.
J. Symb. Comput., 1985

Routing, Merging, and Sorting on Parallel Models of Computation.
J. Comput. Syst. Sci., 1985

1983
Parallel Computation for Well-Endowed Rings and Space-Bounded Probabilistic Machines
Information and Control, 1983

Bounds for Width Two Branching Programs
Proceedings of the 15th Annual ACM Symposium on Theory of Computing, 1983

1982
A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation.
SIAM J. Comput., 1982

Routing, Merging and Sorting on Parallel Models of Computation (Extended Abstract)
Proceedings of the 14th Annual ACM Symposium on Theory of Computing, 1982

Fast Parallel Matrix and GCD Computations
Proceedings of the 23rd Annual Symposium on Foundations of Computer Science, 1982

1981
A Time-Space Tradeoff for Sorting on Non-Oblivious Machines.
J. Comput. Syst. Sci., 1981

Efficient Searching Using Partial Ordering.
Inf. Process. Lett., 1981

1980
A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation
Proceedings of the 12th Annual ACM Symposium on Theory of Computing, 1980

1979
Resource Allocation with Immunity to Limited Process Failure (Preliminary Report)
Proceedings of the 20th Annual Symposium on Foundations of Computer Science, 1979

A Time-Space Tradeoff for Sorting on Non-Oblivious Machines
Proceedings of the 20th Annual Symposium on Foundations of Computer Science, 1979

1977
On Relating Time and Space to Size and Depth.
SIAM J. Comput., 1977

1976
On the Number of Additions to Compute Specific Polynomials.
SIAM J. Comput., 1976

1975
The computational complexity of algebraic and numeric problems.
Elsevier computer science library 1, Elsevier, ISBN: 0444001565, 1975

1974
Social issues in computing: the course.
SIGCAS Computers and Society, 1974

Fast Modular Transforms.
J. Comput. Syst. Sci., 1974

On the Number of Additions to Compute Specific Polynomials (Preliminary Version)
Proceedings of the 6th Annual ACM Symposium on Theory of Computing, April 30, 1974

1972
Efficient Evaluation of Polynomial Forms.
J. Comput. Syst. Sci., 1972

Subrecursive Programming Languages, Part I: efficiency and program structure.
J. ACM, 1972

Corrigendum: "Computational Complexity and the Existence of Complexity Gaps".
J. ACM, 1972

Computational Complexity and the Existence of Complexity Gaps.
J. ACM, 1972

Computers and Employment.
Commun. ACM, 1972

Fast Modular Transforms via Division
Proceedings of the 13th Annual Symposium on Switching and Automata Theory, 1972

1971
Evaluating Polynomials at Many Points.
Inf. Process. Lett., 1971

1970
On the Efficiency of Programs in Subrecursive Formalisms (Incomplete Version, Extended Abstract)
Proceedings of the 11th Annual Symposium on Switching and Automata Theory, 1970

1969
Complexity Classes of Recursive Functions and the Existence of Complexity Gaps
Proceedings of the 1st Annual ACM Symposium on Theory of Computing, 1969

Dense and Non-Dense Families of Complexity Classes
Proceedings of the 10th Annual Symposium on Switching and Automata Theory, 1969


  Loading...