Dense and Non-Dense Families of Complexity Classes - Allan Borodin; Robert L. Constable; John E. Hopcroft (SWAT, 1969)

Complexity Classes of Recursive Functions and the Existence of Complexity Gaps - Allan Borodin (STOC, 1969)

Computational Complexity and the Existence of Complexity Gaps. - Allan Borodin (1969)

On the Efficiency of Programs in Subrecursive Formalisms (Incomplete Version, Extended Abstract) - Robert L. Constable; Allan Borodin (SWAT, 1970)

Evaluating Polynomials at Many Points. - Allan Borodin; J. Ian Munro (Inf. Process. Lett., 1971)

Fast Modular Transforms via Division - R. Moenck; Allan Borodin (SWAT, 1972)

Computers and Employment. - Allan Borodin; C. C. Gotlieb (Commun. ACM, 1972)

Computational Complexity and the Existence of Complexity Gaps. - Allan Borodin (J. ACM, 1972)

Corrigendum: "Computational Complexity and the Existence of Complexity Gaps". - Allan Borodin (J. ACM, 1972)

Subrecursive Programming Languages, Part I: efficiency and program structure. - Robert L. Constable; Allan Borodin (J. ACM, 1972)

Efficient Evaluation of Polynomial Forms. - J. Ian Munro; Allan Borodin (J. Comput. Syst. Sci., 1972)

On the Number of Additions to Compute Specific Polynomials (Preliminary Version) - Allan Borodin; Stephen A. Cook (STOC, 1974)

Fast Modular Transforms. - Allan Borodin; R. Moenck (J. Comput. Syst. Sci., 1974)

Social issues in computing: the course. - C. C. Gotlieb; Allan Borodin (SIGCAS Comput. Soc., 1974)

The computational complexity of algebraic and numeric problems. - Allan Borodin; J. Ian Munro (Elsevier, 1975)

On the Number of Additions to Compute Specific Polynomials. - Allan Borodin; Stephen A. Cook (SIAM J. Comput., 1976)

On Relating Time and Space to Size and Depth. - Allan Borodin (SIAM J. Comput., 1977)

Resource Allocation with Immunity to Limited Process Failure (Preliminary Report) - Michael J. Fischer; Nancy A. Lynch; James E. Burns; Allan Borodin (FOCS, 1979)

A time-space tradeoff for sorting and related non-oblivious computations. - Allan Borodin; Michael J. Fischer; David G. Kirkpatrick; Nancy A. Lynch; Martin Tompa (SIGACT News, 1979)

Efficient Searching Using Partial Ordering. - Allan Borodin; Leonidas J. Guibas; Nancy A. Lynch; Andrew Chi-Chih Yao (Inf. Process. Lett., 1981)

A Time-Space Tradeoff for Sorting on Non-Oblivious Machines. - Allan Borodin; Michael J. Fischer; David G. Kirkpatrick; Nancy A. Lynch; Martin Tompa (J. Comput. Syst. Sci., 1981)

Routing, Merging and Sorting on Parallel Models of Computation (Extended Abstract) - Allan Borodin; John E. Hopcroft (STOC, 1982)

A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation. - Allan Borodin; Stephen A. Cook (SIAM J. Comput., 1982)

Fast Parallel Matrix and GCD Computations - Allan Borodin; Joachim von zur Gathen; John E. Hopcroft (Inf. Control., 1982)

Parallel Computation for Well-Endowed Rings and Space-Bounded Probabilistic Machines - Allan Borodin; Stephen A. Cook; Nicholas Pippenger (Inf. Control., 1983)

Routing, Merging, and Sorting on Parallel Models of Computation. - Allan Borodin; John E. Hopcroft (J. Comput. Syst. Sci., 1985)

Decreasing the Nesting Depth of Expressions Involving Square Roots. - Allan Borodin; Ronald Fagin; John E. Hopcroft; Martin Tompa (J. Symb. Comput., 1985)

Bounds for Width Two Branching Programs. - Allan Borodin; Danny Dolev; Faith E. Fich; Wolfgang J. Paul (SIAM J. Comput., 1986)

An Optimal Online Algorithm for Metrical Task Systems - Allan Borodin; Nathan Linial; Michael E. Saks (STOC, 1987)

A Time-Space Tradeoff for Element Distinctness. - Allan Borodin; Faith E. Fich; Friedhelm Meyer auf der Heide; Eli Upfal; Avi Wigderson (SIAM J. Comput., 1987)

Juris Hartmanis: building a department-building a discipline. - Allan Borodin (SCT, 1988)

Two applications of complementation via inductive counting. - Allan Borodin; Stephen A. Cook; Patrick W. Dymond; Walter L. Ruzzo; Martin Tompa (SCT, 1988)

A Tradeoff Between Search and Update Time for the Implicit Dictionary Problem. - Allan Borodin; Faith E. Fich; Friedhelm Meyer auf der Heide; Eli Upfal; Avi Wigderson (Theor. Comput. Sci., 1988)

Lower Bounds on the Length of Universal Traversal Sequences (Detailed Abstract) - Allan Borodin; Walter L. Ruzzo; Martin Tompa (STOC, 1989)

Bounds on Universal Sequences. - Amotz Bar-Noy; Allan Borodin; Mauricio Karchmer; Nathan Linial; Michael Werman (SIAM J. Comput., 1989)

Two Applications of Inductive Counting for Complementation Problems. - Allan Borodin; Stephen A. Cook; Patrick W. Dymond; Walter L. Ruzzo; Martin Tompa (SIAM J. Comput., 1989)

Erratum: Two Applications of Inductive Counting for Complementation Problems. - Allan Borodin; Stephen A. Cook; Patrick W. Dymond; Walter L. Ruzzo; Martin Tompa (SIAM J. Comput., 1989)

Distributed FIFO Allocation of Identical Resources Using Small Shared Space. - Michael J. Fischer; Nancy A. Lynch; James E. Burns; Allan Borodin (ACM Trans. Program. Lang. Syst., 1989)

Time-Space Tradeoffs for Undirected Graph Traversal - Paul Beame; Allan Borodin; Prabhakar Raghavan; Walter L. Ruzzo; Martin Tompa (FOCS, 1990)

On the Power of Randomization in Online Algorithms (Extended Abstract) - Shai Ben-David; Allan Borodin; Richard M. Karp; Gábor Tardos; Avi Wigderson (STOC, 1990)

On the Decidability of Sparse Univariate Polynomial Interpolation (Preliminary Version) - Allan Borodin; Prasoon Tiwari (STOC, 1990)

Competitive Paging with Locality of Reference (Brief Summary). - Allan Borodin; Sandy Irani; Prabhakar Raghavan; Baruch Schieber (On-Line Algorithms, 1991)

Competitive Paging with Locality of Reference (Preliminary Version) - Allan Borodin; Sandy Irani; Prabhakar Raghavan; Baruch Schieber (STOC, 1991)

On the Decidability of Sparse Univariate Polynomial Interpolation. - Allan Borodin; Prasoon Tiwari (Comput. Complex., 1991)

Can competitive analysis be made competitive? - Allan Borodin (CASCON, 1992)

An Optimal On-Line Algorithm for Metrical Task System. - Allan Borodin; Nathan Linial; Michael E. Saks (J. ACM, 1992)

Lower Bounds on the Length of Universal Traversal Sequences. - Allan Borodin; Walter L. Ruzzo; Martin Tompa (J. Comput. Syst. Sci., 1992)

Time Space Tradeoffs (Getting Closer to the Barrier?). - Allan Borodin (ISAAC, 1993)

Towards a Better Understanding of the Pure Packet Routing. - Allan Borodin (WADS, 1993)

On Lower Bounds for Read-K-Times Branching Programs. - Allan Borodin; Alexander A. Razborov; Roman Smolensky (Comput. Complex., 1993)

A New Measure for the Study of On-Line Algorithms. - Shai Ben-David; Allan Borodin (Algorithmica, 1994)

On the Power of Randomization in On-Line Algorithms. - Shai Ben-David; Allan Borodin; Richard M. Karp; Gábor Tardos; Avi Wigderson (Algorithmica, 1994)

Competitive Paging with Locality of Reference. - Allan Borodin; Sandy Irani; Prabhakar Raghavan; Baruch Schieber (J. Comput. Syst. Sci., 1995)

Adversarial Queueing Theory. - Allan Borodin; Jon M. Kleinberg; Prabhakar Raghavan; Madhu Sudan 001; David P. Williamson (STOC, 1996)

Time-Space Tradeoffs for Undirected Graph Traversal by Graph Automata. - Paul Beame; Allan Borodin; Prabhakar Raghavan; Walter L. Ruzzo; Martin Tompa (Inf. Comput., 1996)

On Ranomization in Online Computation. - Allan Borodin; Ran El-Yaniv (CCC, 1997)

Tribute to Roman Smolensky. - Allan Borodin (Comput. Complex., 1997)

How much can hardware help routing? - Allan Borodin; Prabhakar Raghavan; Baruch Schieber; Eli Upfal (J. ACM, 1997)

Deterministic Many-to-Many Hot Potato Routing. - Allan Borodin; Yuval Rabani; Baruch Schieber (IEEE Trans. Parallel Distributed Syst., 1997)

Online computation and competitive analysis. - Allan Borodin; Ran El-Yaniv (Cambridge University Press, 1998)

Lower Bounds for High Dimensional Nearest Neighbor Search and Related Problems. - Allan Borodin; Rafail Ostrovsky; Yuval Rabani (STOC, 1999)

On Randomization in On-Line Computation. - Allan Borodin; Ran El-Yaniv (Inf. Comput., 1999)

A Time-Space Tradeoff for Undirected Graph Traversal by Walking Automata. - Paul Beame; Allan Borodin; Prabhakar Raghavan; Walter L. Ruzzo; Martin Tompa (SIAM J. Comput., 1999)

On the Competitive Theory and Practice of Portfolio Selection (Extended Abstract). - Allan Borodin; Ran El-Yaniv; Vincent Gogan (LATIN, 2000)

Finding authorities and hubs from link structures on the World Wide Web. - Allan Borodin; Gareth O. Roberts; Jeffrey S. Rosenthal; Panayiotis Tsaparas (WWW, 2001)

Adversarial queuing theory. - Allan Borodin; Jon M. Kleinberg; Prabhakar Raghavan; Madhu Sudan 001; David P. Williamson (J. ACM, 2001)

Perturbation of the Hyper-Linked Environment. - Hyun Chul Lee; Allan Borodin (COCOON, 2003)

(Incremental) Priority Algorithms. - Allan Borodin; Morten N. Nielsen; Charles Rackoff (Algorithmica, 2003)

Priority Algorithms for Graph Optimization Problems. - Allan Borodin; Joan Boyar; Kim S. Larsen (WAOA, 2004)

The Power of Priority Algorithms for Facility Location and Set Cover. - Spyros Angelopoulos 001; Allan Borodin (Algorithmica, 2004)

Can We Learn to Beat the Best Stock. - Allan Borodin; Ran El-Yaniv; Vincent Gogan (J. Artif. Intell. Res., 2004)

Stability Preserving Transformations: Packet Routing Networks with Edge Capacities and Speeds. - Allan Borodin; Rafail Ostrovsky; Yuval Rabani (J. Interconnect. Networks, 2004)

Subquadratic Approximation Algorithms for Clustering Problems in High Dimensional Spaces. - Allan Borodin; Rafail Ostrovsky; Yuval Rabani (Mach. Learn., 2004)

Towards a Theory of Algorithms. - Allan Borodin (WADS, 2005)

Link analysis ranking: algorithms, theory, and experiments. - Allan Borodin; Gareth O. Roberts; Jeffrey S. Rosenthal; Panayiotis Tsaparas (ACM Trans. Internet Techn., 2005)

Further Reflections on a Theory for Basic Algorithms. - Allan Borodin (AAIM, 2006)

Extracting and ranking viral communities using seeds and content similarity. - Hyun Chul Lee; Allan Borodin; Leslie Goldsmith (Hypertext, 2008)

Priority algorithms for the subset-sum problem. - Yuli Ye; Allan Borodin (J. Comb. Optim., 2008)

Invited Talk II The Power and Limitations of Simple Algorithms: A Partial Case Study of Greedy Mechanisim Design for Combinatorial Actions. - Allan Borodin (ALGOSENSORS, 2009)

Cluster Based Personalized Search. - Hyun Chul Lee; Allan Borodin (WAW, 2009)

Toward a Model for Backtracking and Dynamic Programming. - Michael Alekhnovich; Allan Borodin; Joshua Buresh-Oppenheim; Russell Impagliazzo; Avner Magen (Electron. Colloquium Comput. Complex., 2009)

Criteria for Cluster-Based Personalized Search. - Hyun Chul Lee; Allan Borodin (Internet Math., 2009)

On the Relative Merits of Simple Local Search Methods for the MAX-SAT Problem. - Denis Pankratov; Allan Borodin (SAT, 2010)

Price of Anarchy for Greedy Auctions. - Brendan Lucier; Allan Borodin (SODA, 2010)

Threshold Models for Competitive Influence in Social Networks. - Allan Borodin; Yuval Filmus; Joel Oren (WINE, 2010)

Randomized priority algorithms. - Spyros Angelopoulos 001; Allan Borodin (Theor. Comput. Sci., 2010)

Priority algorithms for graph optimization problems. - Allan Borodin; Joan Boyar; Kim S. Larsen; Nazanin Mirmohammadi (Theor. Comput. Sci., 2010)

Toward a Model for Backtracking and Dynamic Programming. - Michael Alekhnovich; Allan Borodin; Joshua Buresh-Oppenheim; Russell Impagliazzo; Avner Magen; Toniann Pitassi (Comput. Complex., 2011)

Special Issue In Memory of Misha Alekhnovich. Foreword. - Allan Borodin; Toniann Pitassi; Alexander A. Razborov (Comput. Complex., 2011)

How well can primal-dual and local-ratio algorithms perform? - Allan Borodin; David Cashman; Avner Magen (ACM Trans. Algorithms, 2011)

Max-Sum diversification, monotone submodular functions and dynamic updates. - Allan Borodin; Hyun Chul Lee; Yuli Ye (PODS, 2012)

Truthful Mechanisms for Competing Submodular Processes - Allan Borodin; Mark Braverman; Brendan Lucier; Joel Oren (CoRR, 2012)

Elimination graphs. - Yuli Ye; Allan Borodin (ACM Trans. Algorithms, 2012)

On sum coloring and sum multi-coloring for restricted families of graphs. - Allan Borodin; Ioana Ivan; Yuli Ye; Bryce Zimny (Theor. Comput. Sci., 2012)

Computing (and Life) Is All about Tradeoffs - A Small Sample of Some Computational Tradeoffs. - Allan Borodin (Space-Efficient Data Structures, Streams, and Algorithms, 2013)

Bounds on Double-Sided Myopic Algorithms for Unconstrained Non-monotone Submodular Maximization. - Norman Huang; Allan Borodin (CoRR, 2013)

Bounds on Double-Sided Myopic Algorithms for Unconstrained Non-monotoneSubmodular Maximization. - Norman Huang; Allan Borodin (ISAAC, 2014)

Weakly Submodular Functions. - Allan Borodin; Dai Le; Yuli Ye (CoRR, 2014)

Budgetary Effects on Pricing Equilibrium in Online Markets. - Allan Borodin; Omer Lev; Tyrone Strangway (AAMAS, 2016)

On the limitations of deterministic de-randomizations for online bipartite matching and max-sat. - Nicolas Pena; Allan Borodin (CoRR, 2016)

On the Limitations of Greedy Mechanism Design for Truthful Combinatorial Auctions. - Allan Borodin; Brendan Lucier (ACM Trans. Economics and Comput., 2016)

Strategyproof Mechanisms for Competitive Influence in Networks. - Allan Borodin; Mark Braverman; Brendan Lucier; Joel Oren (Algorithmica, 2017)

Equilibria of Greedy Combinatorial Auctions. - Brendan Lucier; Allan Borodin (SIAM J. Comput., 2017)

Max-Sum Diversification, Monotone Submodular Functions, and Dynamic Updates. - Allan Borodin; Aadhar Jain; Hyun Chul Lee; Yuli Ye (ACM Trans. Algorithms, 2017)

Sequential Posted-Price Mechanisms with Correlated Valuations. - Marek Adamczyk; Allan Borodin; Diodato Ferraioli; Bart de Keijzer; Stefano Leonardi 001 (ACM Trans. Economics and Comput., 2017)

Greedy Bipartite Matching in Random Type Poisson Arrival Model. - Allan Borodin; Christodoulos Karavasilis; Denis Pankratov (APPROX-RANDOM, 2018)

Seasonal Goods and Spoiled Milk: Pricing for a Limited Shelf-Life. - Atiyeh Ashari Ghomi; Allan Borodin; Omer Lev (AAMAS, 2018)

Big City vs. the Great Outdoors: Voter Distribution and How It Affects Gerrymandering. - Allan Borodin; Omer Lev; Nisarg Shah 001; Tyrone Strangway (IJCAI, 2018)

A Simple PTAS for the Dual Bin Packing Problem and Advice Complexity of Its Online Version. - Allan Borodin; Denis Pankratov; Amirali Salehi-Abari (SOSA, 2018)

Efficient Allocation of Free Stuff. - Yossi Azar; Allan Borodin; Michal Feldman; Amos Fiat; Kineret Segal (AAMAS, 2019)

Electronic markets with multiple submodular buyers. - Allan Borodin; Akash Rakheja (CoRR, 2019)

On Conceptually Simple Algorithms for Variants of Online Bipartite Matching. - Allan Borodin; Denis Pankratov; Amirali Salehi-Abari (Theory Comput. Syst., 2019)

On extensions of the deterministic online model for bipartite matching and max-sat. - Nicolas Pena; Allan Borodin (Theor. Comput. Sci., 2019)

Bipartite Stochastic Matching: Online, Random Order, and I.I.D. Models. - Allan Borodin; Calum MacRury; Akash Rakheja (CoRR, 2020)

Greedy Approaches to Online Stochastic Matching. - Allan Borodin; Calum MacRury; Akash Rakheja (CoRR, 2020)

An Experimental Study of Algorithms for Online Bipartite Matching. - Allan Borodin; Christodoulos Karavasilis; Denis Pankratov (ACM J. Exp. Algorithmics, 2020)

Advice Complexity of Priority Algorithms. - Allan Borodin; Joan Boyar; Kim S. Larsen; Denis Pankratov (Theory Comput. Syst., 2020)

Secretary Matching Meets Probing with Commitment. - Allan Borodin; Calum MacRury; Akash Rakheja (APPROX-RANDOM, 2021)

Prophet Inequality Matching Meets Probing with Commitment. - Allan Borodin; Calum MacRury; Akash Rakheja (CoRR, 2021)

Prophet Matching in the Probe-Commit Model. - Allan Borodin; Calum MacRury; Akash Rakheja (APPROX/RANDOM, 2022)

Little House (Seat) on the Prairie: Compactness, Gerrymandering, and Population Distribution. - Allan Borodin; Omer Lev; Nisarg Shah 001; Tyrone Strangway (AAMAS, 2022)

Distortion in Voting with Top-t Preferences. - Allan Borodin; Daniel Halpern 002; Mohamad Latifian; Nisarg Shah 001 (IJCAI, 2022)

A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation. - Allan Borodin; Stephen A. Cook (Logic, Automata, and Computational Complexity, 2023)

Any-Order Online Interval Selection. - Allan Borodin; Christodoulos Karavasilis (WAOA, 2023)

Online Bipartite Matching in the Probe-Commit Model. - Allan Borodin; Calum MacRury (CoRR, 2023)

Primarily about primaries. - Allan Borodin; Omer Lev; Nisarg Shah 001; Tyrone Strangway (Artif. Intell., 2024)

Random-Order Interval Selection. - Allan Borodin; Christodoulos Karavasilis (CoRR, 2024)

Natural interviewing equilibria in matching settings. - Allan Borodin; Joanna Drummond; Kate Larson; Omer Lev (Soc. Choice Welf., 2025)