default search action
Allan Borodin
Person information
- affiliation: University of Toronto, Canada
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
2020 – today
- 2024
- [j64]Allan Borodin, Omer Lev
, Nisarg Shah, Tyrone Strangway:
Primarily about primaries. Artif. Intell. 329: 104095 (2024) - [i23]Allan Borodin, Christodoulos Karavasilis:
Random-Order Interval Selection. CoRR abs/2407.20941 (2024) - 2023
- [c70]Allan Borodin, Christodoulos Karavasilis:
Any-Order Online Interval Selection. WAOA 2023: 175-189 - [p1]Allan Borodin, Stephen A. Cook:
A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation. Logic, Automata, and Computational Complexity 2023: 245-260 - [i22]Allan Borodin, Christodoulos Karavasilis:
Any-Order Online Interval Selection. CoRR abs/2303.06127 (2023) - [i21]Allan Borodin, Calum MacRury:
Online Bipartite Matching in the Probe-Commit Model. CoRR abs/2303.08908 (2023) - 2022
- [c69]Allan Borodin, Calum MacRury, Akash Rakheja:
Prophet Matching in the Probe-Commit Model. APPROX/RANDOM 2022: 46:1-46:24 - [c68]Allan Borodin, Omer Lev, Nisarg Shah, Tyrone Strangway:
Little House (Seat) on the Prairie: Compactness, Gerrymandering, and Population Distribution. AAMAS 2022: 154-162 - [c67]Allan Borodin, Daniel Halpern, Mohamad Latifian, Nisarg Shah:
Distortion in Voting with Top-t Preferences. IJCAI 2022: 116-122 - 2021
- [c66]Allan Borodin, Calum MacRury, Akash Rakheja:
Secretary Matching Meets Probing with Commitment. APPROX-RANDOM 2021: 13:1-13:23 - [i20]Allan Borodin, Calum MacRury, Akash Rakheja:
Prophet Inequality Matching Meets Probing with Commitment. CoRR abs/2102.04325 (2021) - 2020
- [j63]Allan Borodin, Christodoulos Karavasilis, Denis Pankratov:
An Experimental Study of Algorithms for Online Bipartite Matching. ACM J. Exp. Algorithmics 25: 1-37 (2020) - [j62]Allan Borodin, Joan Boyar
Advice Complexity of Priority Algorithms. Theory Comput. Syst. 64(4): 593-625 (2020) - [i19]Allan Borodin, Calum MacRury, Akash Rakheja:
Bipartite Stochastic Matching: Online, Random Order, and I.I.D. Models. CoRR abs/2004.14304 (2020) - [i18]Allan Borodin, Calum MacRury, Akash Rakheja:
Greedy Approaches to Online Stochastic Matching. CoRR abs/2008.09260 (2020)
2010 – 2019
- 2019
- [j61]Allan Borodin, Denis Pankratov
On Conceptually Simple Algorithms for Variants of Online Bipartite Matching. Theory Comput. Syst. 63(8): 1781-1818 (2019) - [j60]Nicolas Pena
On extensions of the deterministic online model for bipartite matching and max-sat. Theor. Comput. Sci. 770: 1-24 (2019) - [c65]Allan Borodin, Omer Lev, Nisarg Shah, Tyrone Strangway:
Primarily about Primaries. AAAI 2019: 1804-1811 - [c64]Yossi Azar, Allan Borodin, Michal Feldman, Amos Fiat, Kineret Segal:
Efficient Allocation of Free Stuff. AAMAS 2019: 918-925 - [i17]Allan Borodin, Akash Rakheja:
Electronic markets with multiple submodular buyers. CoRR abs/1907.11915 (2019) - 2018
- [c63]Allan Borodin, Christodoulos Karavasilis, Denis Pankratov:
Greedy Bipartite Matching in Random Type Poisson Arrival Model. APPROX-RANDOM 2018: 5:1-5:15 - [c62]Atiyeh Ashari Ghomi, Allan Borodin, Omer Lev:
Seasonal Goods and Spoiled Milk: Pricing for a Limited Shelf-Life. AAMAS 2018: 901-909 - [c61]Allan Borodin, Omer Lev, Nisarg Shah, Tyrone Strangway:
Big City vs. the Great Outdoors: Voter Distribution and How It Affects Gerrymandering. IJCAI 2018: 98-104 - [c60]Allan Borodin, Denis Pankratov, Amirali Salehi-Abari:
A Simple PTAS for the Dual Bin Packing Problem and Advice Complexity of Its Online Version. SOSA 2018: 8:1-8:12 - [c59]Allan Borodin, Joan Boyar
Advice Complexity of Priority Algorithms. WAOA 2018: 69-86 - [i16]Atiyeh Ashari Ghomi, Allan Borodin, Omer Lev:
Seasonal Goods and Spoiled Milk: Pricing for a Limited Shelf-Life. CoRR abs/1801.02263 (2018) - [i15]Allan Borodin, Christodoulos Karavasilis, Denis Pankratov:
Greedy Bipartite Matching in Random Type Poisson Arrival Model. CoRR abs/1805.00578 (2018) - [i14]Allan Borodin, Joan Boyar, Kim S. Larsen, Denis Pankratov:
Advice Complexity of Priority Algorithms. CoRR abs/1806.06223 (2018) - [i13]Allan Borodin, Christodoulos Karavasilis, Denis Pankratov:
An Experimental Study of Algorithms for Online Bipartite Matching. CoRR abs/1808.04863 (2018) - 2017
- [j59]Allan Borodin, Mark Braverman, Brendan Lucier, Joel Oren:
Strategyproof Mechanisms for Competitive Influence in Networks. Algorithmica 78(2): 425-452 (2017) - [j58]Brendan Lucier, Allan Borodin:
Equilibria of Greedy Combinatorial Auctions. SIAM J. Comput. 46(2): 620-660 (2017) - [j57]Allan Borodin, Aadhar Jain, Hyun Chul Lee, Yuli Ye:
Max-Sum Diversification, Monotone Submodular Functions, and Dynamic Updates. ACM Trans. Algorithms 13(3): 41:1-41:25 (2017) - [j56]Marek Adamczyk, Allan Borodin, Diodato Ferraioli, Bart de Keijzer, Stefano Leonardi:
Sequential Posted-Price Mechanisms with Correlated Valuations. ACM Trans. Economics and Comput. 5(4): 22:1-22:39 (2017) - [c58]Allan Borodin, Denis Pankratov, Amirali Salehi-Abari:
On Conceptually Simple Algorithms for Variants of Online Bipartite Matching. WAOA 2017: 253-268 - [i12]Allan Borodin, Denis Pankratov, Amirali Salehi-Abari:
On Conceptually Simple Algorithms for Variants of Online Bipartite Matching. CoRR abs/1706.09966 (2017) - [i11]Allan Borodin, Denis Pankratov, Amirali Salehi-Abari:
A Simple PTAS for the Dual Bin Packing Problem and Advice Complexity of Its Online Version. CoRR abs/1708.01657 (2017) - 2016
- [j55]Allan Borodin, Brendan Lucier:
On the Limitations of Greedy Mechanism Design for Truthful Combinatorial Auctions. ACM Trans. Economics and Comput. 5(1): 2:1-2:23 (2016) - [c57]Allan Borodin, Omer Lev, Tyrone Strangway:
Budgetary Effects on Pricing Equilibrium in Online Markets. AAMAS 2016: 95-103 - [i10]Nicolas Pena, Allan Borodin:
On the limitations of deterministic de-randomizations for online bipartite matching and max-sat. CoRR abs/1608.03182 (2016) - 2015
- [c56]Marek Adamczyk, Allan Borodin, Diodato Ferraioli, Bart de Keijzer, Stefano Leonardi:
Sequential Posted Price Mechanisms with Correlated Valuations. WINE 2015: 1-15 - [i9]Marek Adamczyk, Allan Borodin, Diodato Ferraioli, Bart de Keijzer, Stefano Leonardi:
Sequential Posted Price Mechanisms with Correlated Valuations. CoRR abs/1503.02200 (2015) - [i8]Allan Borodin, Omer Lev, Tyrone Strangway:
Budgetary Effects on Pricing Equilibrium in Online Markets. CoRR abs/1511.06954 (2015) - 2014
- [c55]Norman Huang, Allan Borodin:
Bounds on Double-Sided Myopic Algorithms for Unconstrained Non-monotoneSubmodular Maximization. ISAAC 2014: 528-539 - [i7]Allan Borodin, Dai Le, Yuli Ye:
Weakly Submodular Functions. CoRR abs/1401.6697 (2014) - 2013
- [c54]Allan Borodin:
Computing (and Life) Is All about Tradeoffs - A Small Sample of Some Computational Tradeoffs. Space-Efficient Data Structures, Streams, and Algorithms 2013: 112-132 - [c53]Allan Borodin, Mark Braverman, Brendan Lucier, Joel Oren:
Strategyproof mechanisms for competitive influence in networks. WWW 2013: 141-150 - [i6]Norman Huang, Allan Borodin:
Bounds on Double-Sided Myopic Algorithms for Unconstrained Non-monotone Submodular Maximization. CoRR abs/1312.2173 (2013) - 2012
- [j54]Yuli Ye, Allan Borodin:
Elimination graphs. ACM Trans. Algorithms 8(2): 14:1-14:23 (2012) - [j53]Allan Borodin, Ioana Ivan, Yuli Ye, Bryce Zimny:
On sum coloring and sum multi-coloring for restricted families of graphs. Theor. Comput. Sci. 418: 1-13 (2012) - [c52]Allan Borodin, Hyun Chul Lee, Yuli Ye:
Max-Sum diversification, monotone submodular functions and dynamic updates. PODS 2012: 155-166 - [i5]Allan Borodin, Mark Braverman, Brendan Lucier, Joel Oren:
Truthful Mechanisms for Competing Submodular Processes. CoRR abs/1202.2097 (2012) - [i4]Allan Borodin, Hyun Chul Lee, Yuli Ye:
Max-Sum Diversification, Monotone Submodular Functions and Dynamic Updates. CoRR abs/1203.6397 (2012) - 2011
- [j52]Allan Borodin, Toniann Pitassi, Alexander A. Razborov:
Special Issue In Memory of Misha Alekhnovich. Foreword. Comput. Complex. 20(4): 579-590 (2011) - [j51]Michael Alekhnovich, Allan Borodin, Joshua Buresh-Oppenheim, Russell Impagliazzo
Toward a Model for Backtracking and Dynamic Programming. Comput. Complex. 20(4): 679-740 (2011) - [j50]Allan Borodin, David Cashman, Avner Magen:
How well can primal-dual and local-ratio algorithms perform? ACM Trans. Algorithms 7(3): 29:1-29:26 (2011) - [i3]Allan Borodin, Ran El-Yaniv, Vincent Gogan:
Can We Learn to Beat the Best Stock. CoRR abs/1107.0036 (2011) - 2010
- [j49]Allan Borodin, Joan Boyar
Priority algorithms for graph optimization problems. Theor. Comput. Sci. 411(1): 239-258 (2010) - [j48]Spyros Angelopoulos, Allan Borodin:
Randomized priority algorithms. Theor. Comput. Sci. 411(26-28): 2542-2558 (2010) - [c51]Allan Borodin, Brendan Lucier:
On the Limitations of Greedy Mechanism Design for Truthful Combinatorial Auctions. ICALP (1) 2010: 90-101 - [c50]Denis Pankratov, Allan Borodin:
On the Relative Merits of Simple Local Search Methods for the MAX-SAT Problem. SAT 2010: 223-236 - [c49]Brendan Lucier, Allan Borodin:
Price of Anarchy for Greedy Auctions. SODA 2010: 537-553 - [c48]Allan Borodin, Yuval Filmus, Joel Oren:
Threshold Models for Competitive Influence in Social Networks. WINE 2010: 539-550
2000 – 2009
- 2009
- [j47]Hyun Chul Lee, Allan Borodin:
Criteria for Cluster-Based Personalized Search. Internet Math. 6(3): 399-435 (2009) - [c47]Allan Borodin:
Invited Talk II The Power and Limitations of Simple Algorithms: A Partial Case Study of Greedy Mechanisim Design for Combinatorial Actions. ALGOSENSORS 2009: 2 - [c46]Yuli Ye, Allan Borodin:
Elimination Graphs. ICALP (1) 2009: 774-785 - [c45]Hyun Chul Lee, Allan Borodin:
Cluster Based Personalized Search. WAW 2009: 167-183 - [i2]Brendan Lucier, Allan Borodin:
Price of Anarchy for Greedy Auctions. CoRR abs/0909.0892 (2009) - [i1]Michael Alekhnovich, Allan Borodin, Joshua Buresh-Oppenheim, Russell Impagliazzo, Avner Magen:
Toward a Model for Backtracking and Dynamic Programming. Electron. Colloquium Comput. Complex. TR09 (2009) - 2008
- [j46]Yuli Ye, Allan Borodin:
Priority algorithms for the subset-sum problem. J. Comb. Optim. 16(3): 198-228 (2008) - [c44]Hyun Chul Lee, Allan Borodin, Leslie Goldsmith:
Extracting and ranking viral communities using seeds and content similarity. Hypertext 2008: 139-148 - 2007
- [c43]Yuli Ye, Allan Borodin:
Priority Algorithms for the Subset-Sum Problem. COCOON 2007: 504-514 - 2006
- [c42]Allan Borodin:
Further Reflections on a Theory for Basic Algorithms. AAIM 2006: 1-9 - 2005
- [j45]Allan Borodin, Gareth O. Roberts, Jeffrey S. Rosenthal, Panayiotis Tsaparas
Link analysis ranking: algorithms, theory, and experiments. ACM Trans. Internet Techn. 5(1): 231-297 (2005) - [c41]Michael Alekhnovich, Allan Borodin, Joshua Buresh-Oppenheim, Russell Impagliazzo
Toward a Model for Backtracking and Dynamic Programming. CCC 2005: 308-322 - [c40]Allan Borodin, David Cashman, Avner Magen:
How Well Can Primal-Dual and Local-Ratio Algorithms Perform?. ICALP 2005: 943-955 - [c39]Allan Borodin:
Towards a Theory of Algorithms. WADS 2005: 1 - 2004
- [j44]Spyros Angelopoulos, Allan Borodin:
The Power of Priority Algorithms for Facility Location and Set Cover. Algorithmica 40(4): 271-291 (2004) - [j43]Allan Borodin, Ran El-Yaniv, Vincent Gogan:
Can We Learn to Beat the Best Stock. J. Artif. Intell. Res. 21: 579-594 (2004) - [j42]Allan Borodin, Rafail Ostrovsky, Yuval Rabani
Stability Preserving Transformations: Packet Routing Networks with Edge Capacities and Speeds. J. Interconnect. Networks 5(1): 1-12 (2004) - [j41]Allan Borodin, Rafail Ostrovsky, Yuval Rabani
Subquadratic Approximation Algorithms for Clustering Problems in High Dimensional Spaces. Mach. Learn. 56(1-3): 153-167 (2004) - [c38]Allan Borodin, Joan Boyar, Kim S. Larsen:
Priority Algorithms for Graph Optimization Problems. WAOA 2004: 126-139 - 2003
- [j40]Allan Borodin, Morten N. Nielsen, Charles Rackoff:
(Incremental) Priority Algorithms. Algorithmica 37(4): 295-326 (2003) - [c37]Hyun Chul Lee, Allan Borodin:
Perturbation of the Hyper-Linked Environment. COCOON 2003: 272-283 - [c36]Allan Borodin, Ran El-Yaniv, Vincent Gogan:
Can We Learn to Beat the Best Stock. NIPS 2003: 345-352 - 2002
- [c35]Spyros Angelopoulos, Allan Borodin:
On the Power of Priority Algorithms for Facility Location and Set Cover. APPROX 2002: 26-39 - [c34]Allan Borodin, Morten N. Nielsen, Charles Rackoff:
(Incremental) priority algorithms. SODA 2002: 752-761 - 2001
- [j39]Allan Borodin, Jon M. Kleinberg, Prabhakar Raghavan
Adversarial queuing theory. J. ACM 48(1): 13-38 (2001) - [c33]Allan Borodin, Rafail Ostrovsky, Yuval Rabani:
Stability preserving transformations: packet routing networks with edge capacities and speeds. SODA 2001: 601-610 - [c32]Allan Borodin, Gareth O. Roberts, Jeffrey S. Rosenthal, Panayiotis Tsaparas
Finding authorities and hubs from link structures on the World Wide Web. WWW 2001: 415-429 - 2000
- [c31]Allan Borodin, Ran El-Yaniv, Vincent Gogan:
On the Competitive Theory and Practice of Portfolio Selection (Extended Abstract). LATIN 2000: 173-196
1990 – 1999
- 1999
- [j38]Allan Borodin, Ran El-Yaniv:
On Randomization in On-Line Computation. Inf. Comput. 150(2): 244-267 (1999) - [j37]Paul Beame, Allan Borodin, Prabhakar Raghavan, Walter L. Ruzzo
A Time-Space Tradeoff for Undirected Graph Traversal by Walking Automata. SIAM J. Comput. 28(3): 1051-1072 (1999) - [c30]Allan Borodin, Rafail Ostrovsky, Yuval Rabani
Lower Bounds for High Dimensional Nearest Neighbor Search and Related Problems. STOC 1999: 312-321 - [c29]Allan Borodin, Rafail Ostrovsky, Yuval Rabani
Subquadratic Approximation Algorithms for Clustering Problems in High Dimensional Spaces. STOC 1999: 435-444 - 1998
- [b3]Allan Borodin, Ran El-Yaniv:
Online computation and competitive analysis. Cambridge University Press 1998, ISBN 978-0-521-56392-5, pp. I-XVIII, 1-414 - 1997
- [j36]Allan Borodin:
Tribute to Roman Smolensky. Comput. Complex. 6(3): 195-198 (1997) - [j35]Allan Borodin, Prabhakar Raghavan, Baruch Schieber, Eli Upfal
How much can hardware help routing? J. ACM 44(5): 726-741 (1997) - [j34]Allan Borodin, Yuval Rabani
Deterministic Many-to-Many Hot Potato Routing. IEEE Trans. Parallel Distributed Syst. 8(6): 587-596 (1997) - [c28]Allan Borodin, Ran El-Yaniv:
On Ranomization in Online Computation. CCC 1997: 226-238 - 1996
- [j33]Paul Beame, Allan Borodin, Prabhakar Raghavan
Time-Space Tradeoffs for Undirected Graph Traversal by Graph Automata. Inf. Comput. 130(2): 101-129 (1996) - [c27]Allan Borodin, Jon M. Kleinberg, Prabhakar Raghavan, Madhu Sudan, David P. Williamson:
Adversarial Queueing Theory. STOC 1996: 376-385 - 1995
- [j32]Allan Borodin, Sandy Irani, Prabhakar Raghavan, Baruch Schieber:
Competitive Paging with Locality of Reference. J. Comput. Syst. Sci. 50(2): 244-258 (1995) - [e2]Frank Thomson Leighton, Allan Borodin:
Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 29 May-1 June 1995, Las Vegas, Nevada, USA. ACM 1995, ISBN 0-89791-718-9 [contents] - 1994
- [j31]Shai Ben-David, Allan Borodin, Richard M. Karp, Gábor Tardos
On the Power of Randomization in On-Line Algorithms. Algorithmica 11(1): 2-14 (1994) - [j30]Shai Ben-David, Allan Borodin:
A New Measure for the Study of On-Line Algorithms. Algorithmica 11(1): 73-91 (1994) - 1993
- [j29]Allan Borodin, Alexander A. Razborov, Roman Smolensky:
On Lower Bounds for Read-K-Times Branching Programs. Comput. Complex. 3: 1-18 (1993) - [c26]Allan Borodin:
Time Space Tradeoffs (Getting Closer to the Barrier?). ISAAC 1993: 209-220 - [c25]Allan Borodin, Prabhakar Raghavan, Baruch Schieber, Eli Upfal
How much can hardware help routing? STOC 1993: 573-582 - [c24]Allan Borodin:
Towards a Better Understanding of the Pure Packet Routing. WADS 1993: 14-25 - 1992
- [j28]Allan Borodin, Nathan Linial, Michael E. Saks:
An Optimal On-Line Algorithm for Metrical Task System. J. ACM 39(4): 745-763 (1992) - [j27]Allan Borodin, Walter L. Ruzzo
Lower Bounds on the Length of Universal Traversal Sequences. J. Comput. Syst. Sci. 45(2): 180-203 (1992) - [c23]Allan Borodin:
Can competitive analysis be made competitive? CASCON 1992: 359-367 - 1991
- [j26]Allan Borodin, Prasoon Tiwari:
On the Decidability of Sparse Univariate Polynomial Interpolation. Comput. Complex. 1: 67-90 (1991) - [c22]Allan Borodin, Sandy Irani, Prabhakar Raghavan, Baruch Schieber:
Competitive Paging with Locality of Reference (Brief Summary). On-Line Algorithms 1991: 167-168 - [c21]Allan Borodin, Sandy Irani, Prabhakar Raghavan, Baruch Schieber:
Competitive Paging with Locality of Reference (Preliminary Version). STOC 1991: 249-259 - 1990
- [c20]Paul Beame
Time-Space Tradeoffs for Undirected Graph Traversal. FOCS 1990: 429-438 - [c19]Shai Ben-David, Allan Borodin, Richard M. Karp, Gábor Tardos
On the Power of Randomization in Online Algorithms (Extended Abstract). STOC 1990: 379-386 - [c18]Allan Borodin, Prasoon Tiwari:
On the Decidability of Sparse Univariate Polynomial Interpolation (Preliminary Version). STOC 1990: 535-545
1980 – 1989
- 1989
- [j25]Amotz Bar-Noy, Allan Borodin, Mauricio Karchmer, Nathan Linial, Michael Werman:
Bounds on Universal Sequences. SIAM J. Comput. 18(2): 268-277 (1989) - [j24]Allan Borodin, Stephen A. Cook, Patrick W. Dymond, Walter L. Ruzzo
Two Applications of Inductive Counting for Complementation Problems. SIAM J. Comput. 18(3): 559-578 (1989) - [j23]Allan Borodin, Stephen A. Cook, Patrick W. Dymond, Walter L. Ruzzo
Erratum: Two Applications of Inductive Counting for Complementation Problems. SIAM J. Comput. 18(6): 1283 (1989) - [j22]Michael J. Fischer, Nancy A. Lynch, James E. Burns, Allan Borodin:
Distributed FIFO Allocation of Identical Resources Using Small Shared Space. ACM Trans. Program. Lang. Syst. 11(1): 90-114 (1989) - [c17]Allan Borodin, Walter L. Ruzzo
Lower Bounds on the Length of Universal Traversal Sequences (Detailed Abstract). STOC 1989: 562-573 - 1988
- [j21]Allan Borodin, Faith E. Fich, Friedhelm Meyer auf der Heide, Eli Upfal
A Tradeoff Between Search and Update Time for the Implicit Dictionary Problem. Theor. Comput. Sci. 58: 57-68 (1988) - [c16]Allan Borodin, Stephen A. Cook, Patrick W. Dymond, Walter L. Ruzzo
Two applications of complementation via inductive counting. SCT 1988: 116-125 - [c15]Allan Borodin:
Juris Hartmanis: building a department-building a discipline. SCT 1988: 135-137 - 1987
- [j20]Allan Borodin, Faith E. Fich, Friedhelm Meyer auf der Heide, Eli Upfal
A Time-Space Tradeoff for Element Distinctness. SIAM J. Comput. 16(1): 97-99 (1987) - [c14]Allan Borodin, Nathan Linial, Michael E. Saks:
An Optimal Online Algorithm for Metrical Task Systems. STOC 1987: 373-382 - 1986
- [j19]Allan Borodin, Danny Dolev
Bounds for Width Two Branching Programs. SIAM J. Comput. 15(2): 549-560 (1986) - [c13]Allan Borodin, Faith E. Fich, Friedhelm Meyer auf der Heide, Eli Upfal
A Tradeoff Between Search and Update Time for the Implicit Dictionary Problem. ICALP 1986: 50-59 - [c12]Allan Borodin, Faith E. Fich, Friedhelm Meyer auf der Heide, Eli Upfal
A Time-Space Tradeoff for Element Distinctness. STACS 1986: 353-358 - 1985
- [j18]Allan Borodin, John E. Hopcroft:
Routing, Merging, and Sorting on Parallel Models of Computation. J. Comput. Syst. Sci. 30(1): 130-145 (1985) - [j17]Allan Borodin, Ronald Fagin, John E. Hopcroft, Martin Tompa:
Decreasing the Nesting Depth of Expressions Involving Square Roots. J. Symb. Comput. 1(2): 169-188 (1985) - 1983
- [j16]Allan Borodin, Stephen A. Cook, Nicholas Pippenger:
Parallel Computation for Well-Endowed Rings and Space-Bounded Probabilistic Machines. Inf. Control. 58(1-3): 113-136 (1983) - [c11]Allan Borodin, Danny Dolev, Faith E. Fich, Wolfgang J. Paul:
Bounds for Width Two Branching Programs. STOC 1983: 87-93 - 1982
- [j15]Allan Borodin, Joachim von zur Gathen, John E. Hopcroft:
Fast Parallel Matrix and GCD Computations. Inf. Control. 52(3): 241-256 (1982) - [j14]Allan Borodin, Stephen A. Cook:
A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation. SIAM J. Comput. 11(2): 287-297 (1982) - [c10]Allan Borodin, Joachim von zur Gathen, John E. Hopcroft:
Fast Parallel Matrix and GCD Computations. FOCS 1982: 65-71 - [c9]Allan Borodin, John E. Hopcroft:
Routing, Merging and Sorting on Parallel Models of Computation (Extended Abstract). STOC 1982: 338-344 - 1981
- [j13]Allan Borodin, Leonidas J. Guibas, Nancy A. Lynch, Andrew Chi-Chih Yao:
Efficient Searching Using Partial Ordering. Inf. Process. Lett. 12(2): 71-75 (1981) - [j12]Allan Borodin, Michael J. Fischer, David G. Kirkpatrick, Nancy A. Lynch, Martin Tompa:
A Time-Space Tradeoff for Sorting on Non-Oblivious Machines. J. Comput. Syst. Sci. 22(3): 351-364 (1981) - 1980
- [c8]Allan Borodin, Stephen A. Cook:
A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation. STOC 1980: 294-301
1970 – 1979
- 1979
- [j11]Allan Borodin, Michael J. Fischer, David G. Kirkpatrick, Nancy A. Lynch, Martin Tompa:
A time-space tradeoff for sorting and related non-oblivious computations. SIGACT News 11(2): 24 (1979) - [c7]Michael J. Fischer, Nancy A. Lynch, James E. Burns, Allan Borodin:
Resource Allocation with Immunity to Limited Process Failure (Preliminary Report). FOCS 1979: 234-254 - [c6]Allan Borodin, Michael J. Fischer, David G. Kirkpatrick, Nancy A. Lynch, Martin Tompa:
A Time-Space Tradeoff for Sorting on Non-Oblivious Machines. FOCS 1979: 319-327 - 1977
- [j10]Allan Borodin:
On Relating Time and Space to Size and Depth. SIAM J. Comput. 6(4): 733-744 (1977) - 1976
- [j9]Allan Borodin, Stephen A. Cook:
On the Number of Additions to Compute Specific Polynomials. SIAM J. Comput. 5(1): 146-157 (1976) - 1975
- [b2]Allan Borodin, J. Ian Munro:
The computational complexity of algebraic and numeric problems. Elsevier computer science library 1, Elsevier 1975, ISBN 0444001565, pp. I-X, 1-174 - 1974
- [j8]Allan Borodin, R. Moenck:
Fast Modular Transforms. J. Comput. Syst. Sci. 8(3): 366-386 (1974) - [j7]C. C. Gotlieb, Allan Borodin:
Social issues in computing: the course. SIGCAS Comput. Soc. 5(1): 2 (1974) - [c5]Allan Borodin, Stephen A. Cook:
On the Number of Additions to Compute Specific Polynomials (Preliminary Version). STOC 1974: 342-347 - 1973
- [e1]Alfred V. Aho, Allan Borodin, Robert L. Constable, Robert W. Floyd, Michael A. Harrison, Richard M. Karp, H. Raymond Strong:
Proceedings of the 5th Annual ACM Symposium on Theory of Computing, April 30 - May 2, 1973, Austin, Texas, USA. ACM 1973 [contents] - 1972
- [j6]Allan Borodin, C. C. Gotlieb:
Computers and Employment. Commun. ACM 15(7): 695-702 (1972) - [j5]Allan Borodin:
Computational Complexity and the Existence of Complexity Gaps. J. ACM 19(1): 158-174 (1972) - [j4]Robert L. Constable, Allan Borodin:
Subrecursive Programming Languages, Part I: efficiency and program structure. J. ACM 19(3): 526-568 (1972) - [j3]Allan Borodin:
Corrigendum: "Computational Complexity and the Existence of Complexity Gaps". J. ACM 19(3): 576 (1972) - [j2]J. Ian Munro, Allan Borodin:
Efficient Evaluation of Polynomial Forms. J. Comput. Syst. Sci. 6(6): 625-638 (1972) - [c4]R. Moenck, Allan Borodin:
Fast Modular Transforms via Division. SWAT 1972: 90-96 - 1971
- [j1]Allan Borodin, J. Ian Munro:
Evaluating Polynomials at Many Points. Inf. Process. Lett. 1(2): 66-68 (1971) - 1970
- [c3]Robert L. Constable, Allan Borodin:
On the Efficiency of Programs in Subrecursive Formalisms (Incomplete Version, Extended Abstract). SWAT 1970: 60-67
1960 – 1969
- 1969
- [b1]Allan Borodin:
Computational Complexity and the Existence of Complexity Gaps. Cornell University, USA, 1969 - [c2]Allan Borodin, Robert L. Constable, John E. Hopcroft:
Dense and Non-Dense Families of Complexity Classes. SWAT 1969: 7-19 - [c1]Allan Borodin:
Complexity Classes of Recursive Functions and the Existence of Complexity Gaps. STOC 1969: 67-78
Coauthor Index
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from ,
, and
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and
to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from .
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2024-08-22 20:50 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: