Allan Borodin

167 papers A* 31A 9B 9C 3Misc 2Journal 91Unranked 18
YearRankTypeTitle / Venue / Authors
2026 J jnl
Online Temporal Voting: Strategyproofness, Proportionality and Asymptotic Analysis.
CoRR
Allan Borodin, Tristan Lueger
2025 J jnl
Natural interviewing equilibria in matching settings.
Soc. Choice Welf.
Allan Borodin, Joanna Drummond, Kate Larson, Omer Lev
2025 J jnl
Online Randomness Extraction: Simulating Barely Random Algorithms in the Random Order Arrival Model.
CoRR
Allan Borodin, Christodoulos Karavasilis, David Zhang
2025 J jnl
Online bipartite matching in the probe-commit model.
Math. Program.
Allan Borodin, Calum MacRury
2024 J jnl
Primarily about primaries.
Artif. Intell.
Allan Borodin, Omer Lev, Nisarg Shah, Tyrone Strangway
2024 J jnl
Random-Order Interval Selection.
CoRR
Allan Borodin, Christodoulos Karavasilis
2023 — ch.
A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation.
Logic, Automata, and Computational Complexity
Allan Borodin, Stephen A. Cook
2023 B conf
Any-Order Online Interval Selection.
WAOA
Allan Borodin, Christodoulos Karavasilis
2023 J jnl
Any-Order Online Interval Selection.
CoRR
Allan Borodin, Christodoulos Karavasilis
2023 J jnl
Online Bipartite Matching in the Probe-Commit Model.
CoRR
Allan Borodin, Calum MacRury
2022 A* conf
Distortion in Voting with Top-t Preferences.
IJCAI
Allan Borodin, Daniel Halpern, Mohamad Latifian, Nisarg Shah
2022 A conf
Little House (Seat) on the Prairie: Compactness, Gerrymandering, and Population Distribution.
AAMAS
Allan Borodin, Omer Lev, Nisarg Shah, Tyrone Strangway
2022 A conf
Prophet Matching in the Probe-Commit Model.
APPROX/RANDOM
Allan Borodin, Calum MacRury, Akash Rakheja
2021 J jnl
Prophet Inequality Matching Meets Probing with Commitment.
CoRR
Allan Borodin, Calum MacRury, Akash Rakheja
2021 — conf
Secretary Matching Meets Probing with Commitment.
APPROX-RANDOM
Allan Borodin, Calum MacRury, Akash Rakheja
2020 J jnl
Advice Complexity of Priority Algorithms.
Theory Comput. Syst.
Allan Borodin, Joan Boyar, Kim S. Larsen, Denis Pankratov
2020 J jnl
An Experimental Study of Algorithms for Online Bipartite Matching.
ACM J. Exp. Algorithmics
Allan Borodin, Christodoulos Karavasilis, Denis Pankratov
2020 J jnl
Bipartite Stochastic Matching: Online, Random Order, and I.I.D. Models.
CoRR
Allan Borodin, Calum MacRury, Akash Rakheja
2020 J jnl
Greedy Approaches to Online Stochastic Matching.
CoRR
Allan Borodin, Calum MacRury, Akash Rakheja
2019 A conf
Efficient Allocation of Free Stuff.
AAMAS
Yossi Azar, Allan Borodin, Michal Feldman, Amos Fiat, Kineret Segal
2019 J jnl
Electronic markets with multiple submodular buyers.
CoRR
Allan Borodin, Akash Rakheja
2019 J jnl
On Conceptually Simple Algorithms for Variants of Online Bipartite Matching.
Theory Comput. Syst.
Allan Borodin, Denis Pankratov, Amirali Salehi-Abari
2019 J jnl
On extensions of the deterministic online model for bipartite matching and max-sat.
Theor. Comput. Sci.
Nicolas Pena, Allan Borodin
2019 A* conf
Primarily about Primaries.
AAAI
Allan Borodin, Omer Lev, Nisarg Shah, Tyrone Strangway
2018 — conf
A Simple PTAS for the Dual Bin Packing Problem and Advice Complexity of Its Online Version.
SOSA
Allan Borodin, Denis Pankratov, Amirali Salehi-Abari
2018 B conf
Advice Complexity of Priority Algorithms.
WAOA
Allan Borodin, Joan Boyar, Kim S. Larsen, Denis Pankratov
2018 J jnl
Advice Complexity of Priority Algorithms.
CoRR
Allan Borodin, Joan Boyar, Kim S. Larsen, Denis Pankratov
2018 J jnl
An Experimental Study of Algorithms for Online Bipartite Matching.
CoRR
Allan Borodin, Christodoulos Karavasilis, Denis Pankratov
2018 A* conf
Big City vs. the Great Outdoors: Voter Distribution and How It Affects Gerrymandering.
IJCAI
Allan Borodin, Omer Lev, Nisarg Shah, Tyrone Strangway
2018 — conf
Greedy Bipartite Matching in Random Type Poisson Arrival Model.
APPROX-RANDOM
Allan Borodin, Christodoulos Karavasilis, Denis Pankratov
2018 J jnl
Greedy Bipartite Matching in Random Type Poisson Arrival Model.
CoRR
Allan Borodin, Christodoulos Karavasilis, Denis Pankratov
2018 A conf
Seasonal Goods and Spoiled Milk: Pricing for a Limited Shelf-Life.
AAMAS
Atiyeh Ashari Ghomi, Allan Borodin, Omer Lev
2018 J jnl
Seasonal Goods and Spoiled Milk: Pricing for a Limited Shelf-Life.
CoRR
Atiyeh Ashari Ghomi, Allan Borodin, Omer Lev
2017 J jnl
A Simple PTAS for the Dual Bin Packing Problem and Advice Complexity of Its Online Version.
CoRR
Allan Borodin, Denis Pankratov, Amirali Salehi-Abari
2017 J jnl
Equilibria of Greedy Combinatorial Auctions.
SIAM J. Comput.
Brendan Lucier, Allan Borodin
2017 J jnl
Max-Sum Diversification, Monotone Submodular Functions, and Dynamic Updates.
ACM Trans. Algorithms
Allan Borodin, Aadhar Jain, Hyun Chul Lee, Yuli Ye
2017 B conf
On Conceptually Simple Algorithms for Variants of Online Bipartite Matching.
WAOA
Allan Borodin, Denis Pankratov, Amirali Salehi-Abari
2017 J jnl
On Conceptually Simple Algorithms for Variants of Online Bipartite Matching.
CoRR
Allan Borodin, Denis Pankratov, Amirali Salehi-Abari
2017 J jnl
Sequential Posted-Price Mechanisms with Correlated Valuations.
ACM Trans. Economics and Comput.
Marek Adamczyk, Allan Borodin, Diodato Ferraioli, Bart de Keijzer, Stefano Leonardi
2017 J jnl
Strategyproof Mechanisms for Competitive Influence in Networks.
Algorithmica
Allan Borodin, Mark Braverman, Brendan Lucier, Joel Oren
2016 A conf
Budgetary Effects on Pricing Equilibrium in Online Markets.
AAMAS
Allan Borodin, Omer Lev, Tyrone Strangway
2016 J jnl
On the Limitations of Greedy Mechanism Design for Truthful Combinatorial Auctions.
ACM Trans. Economics and Comput.
Allan Borodin, Brendan Lucier
2016 J jnl
On the limitations of deterministic de-randomizations for online bipartite matching and max-sat.
CoRR
Nicolas Pena, Allan Borodin
2015 J jnl
Budgetary Effects on Pricing Equilibrium in Online Markets.
CoRR
Allan Borodin, Omer Lev, Tyrone Strangway
2015 — conf
Sequential Posted Price Mechanisms with Correlated Valuations.
WINE
Marek Adamczyk, Allan Borodin, Diodato Ferraioli, Bart de Keijzer, Stefano Leonardi
2015 J jnl
Sequential Posted Price Mechanisms with Correlated Valuations.
CoRR
Marek Adamczyk, Allan Borodin, Diodato Ferraioli, Bart de Keijzer, Stefano Leonardi
2014 B conf
Bounds on Double-Sided Myopic Algorithms for Unconstrained Non-monotoneSubmodular Maximization.
ISAAC
Norman Huang, Allan Borodin
2014 J jnl
Weakly Submodular Functions.
CoRR
Allan Borodin, Dai Le, Yuli Ye
2013 J jnl
Bounds on Double-Sided Myopic Algorithms for Unconstrained Non-monotone Submodular Maximization.
CoRR
Norman Huang, Allan Borodin
2013 — conf
Computing (and Life) Is All about Tradeoffs - A Small Sample of Some Computational Tradeoffs.
Space-Efficient Data Structures, Streams, and Algorithms
Allan Borodin
2013 A* conf
Strategyproof mechanisms for competitive influence in networks.
WWW
Allan Borodin, Mark Braverman, Brendan Lucier, Joel Oren
2012 J jnl
Elimination graphs.
ACM Trans. Algorithms
Yuli Ye, Allan Borodin
2012 J jnl
Max-Sum Diversification, Monotone Submodular Functions and Dynamic Updates
CoRR
Allan Borodin, Hyun Chul Lee, Yuli Ye
2012 A* conf
Max-Sum diversification, monotone submodular functions and dynamic updates.
PODS
Allan Borodin, Hyun Chul Lee, Yuli Ye
2012 J jnl
On sum coloring and sum multi-coloring for restricted families of graphs.
Theor. Comput. Sci.
Allan Borodin, Ioana Ivan, Yuli Ye, Bryce Zimny
2012 J jnl
Truthful Mechanisms for Competing Submodular Processes
CoRR
Allan Borodin, Mark Braverman, Brendan Lucier, Joel Oren
2011 J jnl
Can We Learn to Beat the Best Stock
CoRR
Allan Borodin, Ran El-Yaniv, Vincent Gogan
2011 J jnl
How well can primal-dual and local-ratio algorithms perform?
ACM Trans. Algorithms
Allan Borodin, David Cashman, Avner Magen
2011 J jnl
Special Issue In Memory of Misha Alekhnovich. Foreword.
Comput. Complex.
Allan Borodin, Toniann Pitassi, Alexander A. Razborov
2011 J jnl
Toward a Model for Backtracking and Dynamic Programming.
Comput. Complex.
Michael Alekhnovich, Allan Borodin, Joshua Buresh-Oppenheim, Russell Impagliazzo, Avner Magen, Toniann Pitassi
2010 — conf
On the Limitations of Greedy Mechanism Design for Truthful Combinatorial Auctions.
ICALP (1)
Allan Borodin, Brendan Lucier
2010 A conf
On the Relative Merits of Simple Local Search Methods for the MAX-SAT Problem.
SAT
Denis Pankratov, Allan Borodin
2010 A* conf
Price of Anarchy for Greedy Auctions.
SODA
Brendan Lucier, Allan Borodin
2010 J jnl
Priority algorithms for graph optimization problems.
Theor. Comput. Sci.
Allan Borodin, Joan Boyar, Kim S. Larsen, Nazanin Mirmohammadi
2010 J jnl
Randomized priority algorithms.
Theor. Comput. Sci.
Spyros Angelopoulos, Allan Borodin
2010 — conf
Threshold Models for Competitive Influence in Social Networks.
WINE
Allan Borodin, Yuval Filmus, Joel Oren
2009 C conf
Cluster Based Personalized Search.
WAW
Hyun Chul Lee, Allan Borodin
2009 J jnl
Criteria for Cluster-Based Personalized Search.
Internet Math.
Hyun Chul Lee, Allan Borodin
2009 — conf
Elimination Graphs.
ICALP (1)
Yuli Ye, Allan Borodin
2009 C conf
Invited Talk II The Power and Limitations of Simple Algorithms: A Partial Case Study of Greedy Mechanisim Design for Combinatorial Actions.
ALGOSENSORS
Allan Borodin
2009 J jnl
Price of Anarchy for Greedy Auctions
CoRR
Brendan Lucier, Allan Borodin
2009 J jnl
Toward a Model for Backtracking and Dynamic Programming.
Electron. Colloquium Comput. Complex.
Michael Alekhnovich, Allan Borodin, Joshua Buresh-Oppenheim, Russell Impagliazzo, Avner Magen
2008 — conf
Extracting and ranking viral communities using seeds and content similarity.
Hypertext
Hyun Chul Lee, Allan Borodin, Leslie Goldsmith
2008 J jnl
Priority algorithms for the subset-sum problem.
J. Comb. Optim.
Yuli Ye, Allan Borodin
2007 Misc conf
Priority Algorithms for the Subset-Sum Problem.
COCOON
Yuli Ye, Allan Borodin
2006 C conf
Further Reflections on a Theory for Basic Algorithms.
AAIM
Allan Borodin
2005 A* conf
How Well Can Primal-Dual and Local-Ratio Algorithms Perform?.
ICALP
Allan Borodin, David Cashman, Avner Magen
2005 J jnl
Link analysis ranking: algorithms, theory, and experiments.
ACM Trans. Internet Techn.
Allan Borodin, Gareth O. Roberts, Jeffrey S. Rosenthal, Panayiotis Tsaparas
2005 A conf
Toward a Model for Backtracking and Dynamic Programming.
CCC
Michael Alekhnovich, Allan Borodin, Joshua Buresh-Oppenheim, Russell Impagliazzo, Avner Magen, Toniann Pitassi
2005 B conf
Towards a Theory of Algorithms.
WADS
Allan Borodin
2004 J jnl
Can We Learn to Beat the Best Stock.
J. Artif. Intell. Res.
Allan Borodin, Ran El-Yaniv, Vincent Gogan
2004 B conf
Priority Algorithms for Graph Optimization Problems.
WAOA
Allan Borodin, Joan Boyar, Kim S. Larsen
2004 J jnl
Stability Preserving Transformations: Packet Routing Networks with Edge Capacities and Speeds.
J. Interconnect. Networks
Allan Borodin, Rafail Ostrovsky, Yuval Rabani
2004 J jnl
Subquadratic Approximation Algorithms for Clustering Problems in High Dimensional Spaces.
Mach. Learn.
Allan Borodin, Rafail Ostrovsky, Yuval Rabani
2004 J jnl
The Power of Priority Algorithms for Facility Location and Set Cover.
Algorithmica
Spyros Angelopoulos, Allan Borodin
2003 J jnl
(Incremental) Priority Algorithms.
Algorithmica
Allan Borodin, Morten N. Nielsen, Charles Rackoff
2003 — conf
Can We Learn to Beat the Best Stock.
NIPS
Allan Borodin, Ran El-Yaniv, Vincent Gogan
2003 Misc conf
Perturbation of the Hyper-Linked Environment.
COCOON
Hyun Chul Lee, Allan Borodin
2002 A* conf
(Incremental) priority algorithms.
SODA
Allan Borodin, Morten N. Nielsen, Charles Rackoff
2002 — conf
On the Power of Priority Algorithms for Facility Location and Set Cover.
APPROX
Spyros Angelopoulos, Allan Borodin
2001 J jnl
Adversarial queuing theory.
J. ACM
Allan Borodin, Jon M. Kleinberg, Prabhakar Raghavan, Madhu Sudan, David P. Williamson
2001 A* conf
Finding authorities and hubs from link structures on the World Wide Web.
WWW
Allan Borodin, Gareth O. Roberts, Jeffrey S. Rosenthal, Panayiotis Tsaparas
2001 A* conf
Stability preserving transformations: packet routing networks with edge capacities and speeds.
SODA
Allan Borodin, Rafail Ostrovsky, Yuval Rabani
2000 B conf
On the Competitive Theory and Practice of Portfolio Selection (Extended Abstract).
LATIN
Allan Borodin, Ran El-Yaniv, Vincent Gogan
1999 J jnl
A Time-Space Tradeoff for Undirected Graph Traversal by Walking Automata.
SIAM J. Comput.
Paul Beame, Allan Borodin, Prabhakar Raghavan, Walter L. Ruzzo, Martin Tompa
1999 A* conf
Lower Bounds for High Dimensional Nearest Neighbor Search and Related Problems.
STOC
Allan Borodin, Rafail Ostrovsky, Yuval Rabani
1999 J jnl
On Randomization in On-Line Computation.
Inf. Comput.
Allan Borodin, Ran El-Yaniv
1999 A* conf
Subquadratic Approximation Algorithms for Clustering Problems in High Dimensional Spaces.
STOC
Allan Borodin, Rafail Ostrovsky, Yuval Rabani
1998 — book
Online computation and competitive analysis.
Allan Borodin, Ran El-Yaniv
1997 J jnl
Deterministic Many-to-Many Hot Potato Routing.
IEEE Trans. Parallel Distributed Syst.
Allan Borodin, Yuval Rabani, Baruch Schieber
1997 J jnl
How much can hardware help routing?
J. ACM
Allan Borodin, Prabhakar Raghavan, Baruch Schieber, Eli Upfal
1997 A conf
On Ranomization in Online Computation.
CCC
Allan Borodin, Ran El-Yaniv
1997 J jnl
Tribute to Roman Smolensky.
Comput. Complex.
Allan Borodin
1996 A* conf
Adversarial Queueing Theory.
STOC
Allan Borodin, Jon M. Kleinberg, Prabhakar Raghavan, Madhu Sudan, David P. Williamson
1996 J jnl
Time-Space Tradeoffs for Undirected Graph Traversal by Graph Automata.
Inf. Comput.
Paul Beame, Allan Borodin, Prabhakar Raghavan, Walter L. Ruzzo, Martin Tompa
1995 J jnl
Competitive Paging with Locality of Reference.
J. Comput. Syst. Sci.
Allan Borodin, Sandy Irani, Prabhakar Raghavan, Baruch Schieber
1995 A* ed.
Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 29 May-1 June 1995, Las Vegas, Nevada, USA
STOC
Frank Thomson Leighton, Allan Borodin
1994 J jnl
A New Measure for the Study of On-Line Algorithms.
Algorithmica
Shai Ben-David, Allan Borodin
1994 J jnl
On the Power of Randomization in On-Line Algorithms.
Algorithmica
Shai Ben-David, Allan Borodin, Richard M. Karp, Gábor Tardos, Avi Wigderson
1993 A* conf
How much can hardware help routing?
STOC
Allan Borodin, Prabhakar Raghavan, Baruch Schieber, Eli Upfal
1993 J jnl
On Lower Bounds for Read-K-Times Branching Programs.
Comput. Complex.
Allan Borodin, Alexander A. Razborov, Roman Smolensky
1993 B conf
Time Space Tradeoffs (Getting Closer to the Barrier?).
ISAAC
Allan Borodin
1993 B conf
Towards a Better Understanding of the Pure Packet Routing.
WADS
Allan Borodin
1992 J jnl
An Optimal On-Line Algorithm for Metrical Task System.
J. ACM
Allan Borodin, Nathan Linial, Michael E. Saks
1992 — conf
Can competitive analysis be made competitive?
CASCON
Allan Borodin
1992 J jnl
Lower Bounds on the Length of Universal Traversal Sequences.
J. Comput. Syst. Sci.
Allan Borodin, Walter L. Ruzzo, Martin Tompa
1991 — conf
Competitive Paging with Locality of Reference (Brief Summary).
On-Line Algorithms
Allan Borodin, Sandy Irani, Prabhakar Raghavan, Baruch Schieber
1991 A* conf
Competitive Paging with Locality of Reference (Preliminary Version)
STOC
Allan Borodin, Sandy Irani, Prabhakar Raghavan, Baruch Schieber
1991 J jnl
On the Decidability of Sparse Univariate Polynomial Interpolation.
Comput. Complex.
Allan Borodin, Prasoon Tiwari
1990 A* conf
On the Decidability of Sparse Univariate Polynomial Interpolation (Preliminary Version)
STOC
Allan Borodin, Prasoon Tiwari
1990 A* conf
On the Power of Randomization in Online Algorithms (Extended Abstract)
STOC
Shai Ben-David, Allan Borodin, Richard M. Karp, Gábor Tardos, Avi Wigderson
1990 A* conf
Time-Space Tradeoffs for Undirected Graph Traversal
FOCS
Paul Beame, Allan Borodin, Prabhakar Raghavan, Walter L. Ruzzo, Martin Tompa
1989 J jnl
Bounds on Universal Sequences.
SIAM J. Comput.
Amotz Bar-Noy, Allan Borodin, Mauricio Karchmer, Nathan Linial, Michael Werman
1989 J jnl
Distributed FIFO Allocation of Identical Resources Using Small Shared Space.
ACM Trans. Program. Lang. Syst.
Michael J. Fischer, Nancy A. Lynch, James E. Burns, Allan Borodin
1989 J jnl
Erratum: Two Applications of Inductive Counting for Complementation Problems.
SIAM J. Comput.
Allan Borodin, Stephen A. Cook, Patrick W. Dymond, Walter L. Ruzzo, Martin Tompa
1989 A* conf
Lower Bounds on the Length of Universal Traversal Sequences (Detailed Abstract)
STOC
Allan Borodin, Walter L. Ruzzo, Martin Tompa
1989 J jnl
Two Applications of Inductive Counting for Complementation Problems.
SIAM J. Comput.
Allan Borodin, Stephen A. Cook, Patrick W. Dymond, Walter L. Ruzzo, Martin Tompa
1988 J jnl
A Tradeoff Between Search and Update Time for the Implicit Dictionary Problem.
Theor. Comput. Sci.
Allan Borodin, Faith E. Fich, Friedhelm Meyer auf der Heide, Eli Upfal, Avi Wigderson
1988 — conf
Juris Hartmanis: building a department-building a discipline.
SCT
Allan Borodin
1988 — conf
Two applications of complementation via inductive counting.
SCT
Allan Borodin, Stephen A. Cook, Patrick W. Dymond, Walter L. Ruzzo, Martin Tompa
1987 J jnl
A Time-Space Tradeoff for Element Distinctness.
SIAM J. Comput.
Allan Borodin, Faith E. Fich, Friedhelm Meyer auf der Heide, Eli Upfal, Avi Wigderson
1987 A* conf
An Optimal Online Algorithm for Metrical Task Systems
STOC
Allan Borodin, Nathan Linial, Michael E. Saks
1986 A conf
A Time-Space Tradeoff for Element Distinctness.
STACS
Allan Borodin, Faith E. Fich, Friedhelm Meyer auf der Heide, Eli Upfal, Avi Wigderson
1986 A* conf
A Tradeoff Between Search and Update Time for the Implicit Dictionary Problem.
ICALP
Allan Borodin, Faith E. Fich, Friedhelm Meyer auf der Heide, Eli Upfal, Avi Wigderson
1986 J jnl
Bounds for Width Two Branching Programs.
SIAM J. Comput.
Allan Borodin, Danny Dolev, Faith E. Fich, Wolfgang J. Paul
1985 J jnl
Decreasing the Nesting Depth of Expressions Involving Square Roots.
J. Symb. Comput.
Allan Borodin, Ronald Fagin, John E. Hopcroft, Martin Tompa
1985 J jnl
Routing, Merging, and Sorting on Parallel Models of Computation.
J. Comput. Syst. Sci.
Allan Borodin, John E. Hopcroft
1983 A* conf
Bounds for Width Two Branching Programs
STOC
Allan Borodin, Danny Dolev, Faith E. Fich, Wolfgang J. Paul
1983 J jnl
Parallel Computation for Well-Endowed Rings and Space-Bounded Probabilistic Machines
Inf. Control.
Allan Borodin, Stephen A. Cook, Nicholas Pippenger
1982 J jnl
A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation.
SIAM J. Comput.
Allan Borodin, Stephen A. Cook
1982 A* conf
Fast Parallel Matrix and GCD Computations
FOCS
Allan Borodin, Joachim von zur Gathen, John E. Hopcroft
1982 J jnl
Fast Parallel Matrix and GCD Computations
Inf. Control.
Allan Borodin, Joachim von zur Gathen, John E. Hopcroft
1982 A* conf
Routing, Merging and Sorting on Parallel Models of Computation (Extended Abstract)
STOC
Allan Borodin, John E. Hopcroft
1981 J jnl
A Time-Space Tradeoff for Sorting on Non-Oblivious Machines.
J. Comput. Syst. Sci.
Allan Borodin, Michael J. Fischer, David G. Kirkpatrick, Nancy A. Lynch, Martin Tompa
1981 J jnl
Efficient Searching Using Partial Ordering.
Inf. Process. Lett.
Allan Borodin, Leonidas J. Guibas, Nancy A. Lynch, Andrew Chi-Chih Yao
1980 A* conf
A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation
STOC
Allan Borodin, Stephen A. Cook
1979 A* conf
A Time-Space Tradeoff for Sorting on Non-Oblivious Machines
FOCS
Allan Borodin, Michael J. Fischer, David G. Kirkpatrick, Nancy A. Lynch, Martin Tompa
1979 J jnl
A time-space tradeoff for sorting and related non-oblivious computations.
SIGACT News
Allan Borodin, Michael J. Fischer, David G. Kirkpatrick, Nancy A. Lynch, Martin Tompa
1979 A* conf
Resource Allocation with Immunity to Limited Process Failure (Preliminary Report)
FOCS
Michael J. Fischer, Nancy A. Lynch, James E. Burns, Allan Borodin
1977 J jnl
On Relating Time and Space to Size and Depth.
SIAM J. Comput.
Allan Borodin
1976 J jnl
On the Number of Additions to Compute Specific Polynomials.
SIAM J. Comput.
Allan Borodin, Stephen A. Cook
1975 — book
The computational complexity of algebraic and numeric problems.
Allan Borodin, J. Ian Munro
1974 J jnl
Fast Modular Transforms.
J. Comput. Syst. Sci.
Allan Borodin, R. Moenck
1974 A* conf
On the Number of Additions to Compute Specific Polynomials (Preliminary Version)
STOC
Allan Borodin, Stephen A. Cook
1974 J jnl
Social issues in computing: the course.
SIGCAS Comput. Soc.
C. C. Gotlieb, Allan Borodin
1973 A* ed.
Proceedings of the 5th Annual ACM Symposium on Theory of Computing, April 30 - May 2, 1973, Austin, Texas, USA
STOC
Alfred V. Aho, Allan Borodin, Robert L. Constable, Robert W. Floyd, Michael A. Harrison, Richard M. Karp, H. Raymond Strong
1972 J jnl
Computational Complexity and the Existence of Complexity Gaps.
J. ACM
Allan Borodin
1972 J jnl
Computers and Employment.
Commun. ACM
Allan Borodin, C. C. Gotlieb
1972 J jnl
Corrigendum: "Computational Complexity and the Existence of Complexity Gaps".
J. ACM
Allan Borodin
1972 J jnl
Efficient Evaluation of Polynomial Forms.
J. Comput. Syst. Sci.
J. Ian Munro, Allan Borodin
1972 — conf
Fast Modular Transforms via Division
SWAT
R. Moenck, Allan Borodin
1972 J jnl
Subrecursive Programming Languages, Part I: efficiency and program structure.
J. ACM
Robert L. Constable, Allan Borodin
1971 J jnl
Evaluating Polynomials at Many Points.
Inf. Process. Lett.
Allan Borodin, J. Ian Munro
1970 — conf
On the Efficiency of Programs in Subrecursive Formalisms (Incomplete Version, Extended Abstract)
SWAT
Robert L. Constable, Allan Borodin
1969 A* conf
Complexity Classes of Recursive Functions and the Existence of Complexity Gaps
STOC
Allan Borodin
1969 — —
Computational Complexity and the Existence of Complexity Gaps.
Allan Borodin
1969 — conf
Dense and Non-Dense Families of Complexity Classes
SWAT
Allan Borodin, Robert L. Constable, John E. Hopcroft