Allan Borodin
#48,484
Most Influential Person Now
American computer scientist
Allan Borodin's AcademicInfluence.com Rankings
Allan Borodincomputer-science Degrees
Computer Science
#1928
World Rank
#2002
Historical Rank
Theoretical Computer Science
#38
World Rank
#38
Historical Rank
Database
#5479
World Rank
#5684
Historical Rank
Download Badge
Computer Science
Why Is Allan Borodin Influential?
(Suggest an Edit or Addition)According to Wikipedia, Allan Bertram Borodin is a Canadian-American computer scientist who is a professor at the University of Toronto. Biography Borodin did his undergraduate studies at Rutgers University, earning a bachelor's degree in mathematics in 1963. After earning a master's degree at the Stevens Institute of Technology in 1966 , he continued his graduate studies at Cornell University, completing a doctorate in 1969 under the supervision of Juris Hartmanis. He joined the Toronto faculty in 1969 and was promoted to full professor in 1977. He served as department chair from 1980 to 1985, and became University Professor in 2011.
Allan Borodin's Published Works
Number of citations in a given year to any of this author's works
Total number of citations to an author for the works they published in a given year. This highlights publication of the most important work(s) by the author
Published Works
- Online computation and competitive analysis (1998) (2489)
- The computational complexity of algebraic and numeric problems (1975) (433)
- On Relating Time and Space to Size and Depth (1977) (351)
- Link analysis ranking: algorithms, theory, and experiments (2005) (343)
- An optimal on-line algorithm for metrical task system (1992) (338)
- Threshold Models for Competitive Influence in Social Networks (2010) (316)
- Finding authorities and hubs from link structures on the World Wide Web (2001) (284)
- Fast parallel matrix and GCD computations (1982) (265)
- Routing, Merging, and Sorting on Parallel Models of Computation (1985) (262)
- Adversarial queuing theory (2001) (257)
- Competitive paging with locality of reference (1991) (257)
- Routing, merging and sorting on parallel models of computation (1982) (248)
- An optimal online algorithm for metrical task systems (1987) (238)
- Can We Learn to Beat the Best Stock (2003) (213)
- On the power of randomization in online algorithms (1990) (210)
- On the power of randomization in on-line algorithms (2005) (196)
- Adversarial queueing theory (1996) (188)
- Parallel Computation for Well-Endowed Rings and Space-Bounded Probabilistic Machines (1984) (156)
- A time-space tradeoff for sorting on a general sequential model of computation (1980) (155)
- Two Applications of Inductive Counting for Complementation Problems (1989) (142)
- Max-Sum diversification, monotone submodular functions and dynamic updates (2012) (117)
- Lower bounds for high dimensional nearest neighbor search and related problems (1999) (112)
- Resource allocation with immunity to limited process failure (1979) (110)
- Price of anarchy for greedy auctions (2009) (104)
- A new measure for the study of on-line algorithms (2005) (102)
- A time-space tradeoff for sorting on non-oblivious machines (1979) (99)
- Fast Modular Transforms via Division (1972) (95)
- (Incremental) Priority Algorithms (2002) (95)
- Distributed FIFO allocation of identical resources using small shared space (1985) (85)
- Fast Modular Transforms (1974) (80)
- On lower bounds for read-k-times branching programs (2005) (77)
- On the Number of Additions to Compute Specific Polynomials (1976) (76)
- Computational Complexity and the Existence of Complexity Gaps (1972) (75)
- Bounds for width two branching programs (1983) (61)
- Toward a Model for Backtracking and Dynamic Programming (2005) (58)
- On the Competitive Theory and Practice of Portfolio Selection (Extended Abstract) (2000) (52)
- Subquadratic Approximation Algorithms for Clustering Problems in High Dimensional Spaces (1999) (51)
- Deterministic Many-to-Many Hot Potato Routing (1997) (51)
- A Time-Space Tradeoff for Element Distinctness (1987) (48)
- Elimination graphs (2009) (47)
- Some Comments on Functional Self-Reducibility and the NP Hierarchy (1976) (45)
- Lower bounds on the length of universal traversal sequences (1989) (37)
- Max-Sum Diversification, Monotone Submodular Functions, and Dynamic Updates (2017) (37)
- Complexity Classes of Recursive Functions and the Existence of Complexity Gaps (1969) (36)
- Subrecursive Programming Languages, Part I: efficiency and program structure (1972) (36)
- Stability preserving transformations: packet routing networks with edge capacities and speeds (2001) (36)
- Decreasing the Nesting Depth of Expressions Involving Square Roots (1985) (35)
- Efficient Searching Using Partial Ordering (1981) (34)
- Time Space Tradeoffs (Getting Closer to the Barrier?) (1993) (32)
- Priority algorithms for graph optimization problems (2004) (32)
- Two applications of complementation via inductive counting (1988) (32)
- The Power of Priority Algorithms for Facility Location and Set Cover (2004) (31)
- Big City vs. the Great Outdoors: Voter Distribution and How It Affects Gerrymandering (2018) (31)
- Strategyproof Mechanisms for Competitive Influence in Networks (2013) (30)
- Bounds on Universal Sequences (1989) (29)
- A Tradeoff Between Search and Update Time for the Implicit Dictionary Problem (1986) (28)
- Sequential Posted-Price Mechanisms with Correlated Valuations (2015) (26)
- On the decidability of sparse univariate polynomial interpolation (1991) (25)
- Time-space tradeoffs for undirected graph traversal (1990) (22)
- On randomization in online computation (1997) (21)
- Perturbation of the Hyper-Linked Environment (2003) (21)
- Primarily about Primaries (2019) (21)
- On Randomization in On-Line Computation (1999) (21)
- How much can hardware help routing? (1997) (21)
- Dense and Non-Dense Families of Complexity Classes (1969) (20)
- Evaluating Polynomials at Many Points (1971) (20)
- How well can primal-dual and local-ratio algorithms perform? (2005) (18)
- PROBLEMS AND ISSUES (1973) (17)
- Randomized priority algorithms (2010) (17)
- On the Power of Priority Algorithms for Facility Location and Set Cover (2002) (17)
- Bounds on Double-Sided Myopic Algorithms for Unconstrained Non-monotoneSubmodular Maximization (2013) (16)
- HORNERS RULE IS UNIQUELY OPTIMAL (1971) (16)
- Weakly Submodular Functions (2014) (15)
- On the Efficiency of Programs in Subrecursive Formalisms (Incomplete Version, Extended Abstract) (1970) (14)
- A time-space tradeoff for sorting and related non-oblivious computations (1979) (14)
- On sum coloring and sum multi-coloring for restricted families of graphs (2012) (14)
- Time-Space Tradeoffs for Undirected Graph Traversal by Graph Automata (1996) (13)
- How much can hardware help routing? (1993) (12)
- On the Decidability of Sparse Univariate Polynomial Interpolation (Preliminary Version) (1990) (12)
- On the Limitations of Greedy Mechanism Design for Truthful Combinatorial Auctions (2010) (11)
- An Experimental Study of Algorithms for Online Bipartite Matching (2018) (9)
- On Conceptually Simple Algorithms for Variants of Online Bipartite Matching (2017) (9)
- Budgetary Effects on Pricing Equilibrium in Online Markets (2015) (9)
- Parallel Computation for Well-Endowed Rings (1983) (9)
- A Time-Space Tradeoff for Undirected Graph Traversal by Walking Automata (1999) (8)
- Bipartite Stochastic Matching: Online, Random Order, and I.I.D. Models (2020) (8)
- Introduction to Computer Science. Problems, Algorithms, Languages, Information and Computers. (1970) (8)
- Priority algorithms for the subset-sum problem (2007) (8)
- On the Relative Merits of Simple Local Search Methods for the MAX-SAT Problem (2010) (7)
- Erratum: Two Applications of Inductive Counting for Complementation Problems (1989) (7)
- Merging on Parallel Models of Computation (1981) (7)
- Corrigendum: `` Computational Complexity and the Existence of Complexity Gaps'' (1972) (6)
- Computers and employment (1972) (6)
- Efficient Evaluation of Polynomial Forms (1972) (6)
- On extensions of the deterministic online model for bipartite matching and max-sat (2019) (5)
- SHIFTS IN POWER (1973) (5)
- Distortion in Voting with Top-t Preferences (2022) (5)
- Greedy Mechanism Design for Truthful Combinatorial Auctions (2009) (5)
- Extracting and ranking viral communities using seeds and content similarity (2008) (4)
- Criteria for Cluster-Based Personalized Search (2009) (4)
- On the number of additions to compute specific polynomials (Preliminary Version) (1974) (4)
- Natural Interviewing Equilibria for Stable Matching (2016) (4)
- A Simple PTAS for the Dual Bin Packing Problem and Advice Complexity of Its Online Version (2017) (4)
- Prophet Inequality Matching Meets Probing with Commitment (2021) (4)
- A Proportionally Submodular Functions (2015) (4)
- Competitive Paging with Locality of Reference (Preliminary Version) (1991) (3)
- On the limitations of deterministic de-randomizations for online bipartite matching and max-sat (2016) (3)
- Greedy Bipartite Matching in Random Type Poisson Arrival Model (2018) (3)
- Cluster Based Personalized Search (2009) (3)
- Greedy Approaches to Online Stochastic Matching (2020) (3)
- On the complexity of thest-connectivity problem (1995) (2)
- Towards a Theory of Algorithms (2005) (2)
- Prophet Matching Meets Probing with Commitment (2021) (2)
- Efficient Allocation of Free Stuff (2019) (2)
- Advice Complexity of Priority Algorithms (2018) (2)
- Seasonal Goods and Spoiled Milk: Pricing for a Limited Shelf-Life (2018) (2)
- INFORMATION SYSTEMS AND PRIVACY (1973) (1)
- Can competitive analysis be made competitive? (1992) (1)
- IV / FAST PARALLEL MATRIX AND GCD COMPUTATIONS (1)
- Strategyproof Mechanisms for Competitive Influence in Networks (2016) (1)
- Juris Hartmanis: building a department-building a discipline (1988) (1)
- A Faster Approximate Minimum Steiner Tree Algorithm & Primal-Dual and Local-Ratio Greedy Algorithms (2009) (1)
- Invited Talk II The Power and Limitations of Simple Algorithms: A Partial Case Study of Greedy Mechanisim Design for Combinatorial Actions (2009) (1)
- Sequential Elimination Graphs ⋆ (2009) (1)
- Advice Complexity of Priority Algorithms (2019) (1)
- Routing in Networks (1981) (1)
- Social and Information Networks (2019) (1)
- Equilibria of Greedy Combinatorial Auctions (2017) (1)
- On Conceptually Simple Algorithms for Variants of Online Bipartite Matching (2019) (1)
- Truthful Mechanisms for Competing Submodular Processes (2012) (1)
- Social issues in computing: the course (1974) (1)
- Emcient Evaluation of Polynomial Forms (1972) (1)
- Further Reflections on a Theory for Basic Algorithms (2006) (1)
- Little House (Seat) on the Prairie: Compactness, Gerrymandering, and Population Distribution (2022) (0)
- The Computational complexity of algebraic problems (2017) (0)
- COMPUTER CAPABILITIES AND LIMITATIONS (1973) (0)
- Online Bipartite Matching in the Probe-Commit Model (2023) (0)
- Csc2420: Algorithm Design, Analysis and Theory Topic: Markov Chain and Randomized Rounding 22.1 Outline 22.2 Markov Chain 22.2.1 the Basics (2010) (0)
- Session details: Session 3B (2002) (0)
- PROFESSIONALIZATION AND RESPONSIBILITY (1973) (0)
- SURVEYING AND PREDICTING (1973) (0)
- Computing (and Life) Is All about Tradeoffs - A Small Sample of Some Computational Tradeoffs (2013) (0)
- Csc2420: Algorithm Design, Analysis and Theory Lecture Notes 8: Sublinear Algorithms (2011) (0)
- SYSTEMS, MODELS, AND SIMULATIONS (1973) (0)
- Special Issue In Memory of Misha Alekhnovich. Foreword (2011) (0)
- Online and Other Myopic Algorithms (2021) (0)
- 1 The makespan problem for identical machines — continued (2011) (0)
- Incremental) priority algorithms YYYY No org found YYY (2002) (0)
- Csc2420 -fall 2010 -lecture 5 1 Weighted Set Cover Problem (2010) (0)
- Any-Order Online Interval Selection (2023) (0)
- 5. Conclusion and Open Problems Step 4.3 for Each Internal Node Build Tablem , 1 for Array M in M , Level of the Tree Number of Children per Node (0)
- Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 29 May-1 June 1995, Las Vegas, Nevada, USA (1995) (0)
- THE DISTRIBUTION OF COMPUTER PRODUCTS AND SERVICES (1973) (0)
- FILES, DATA BANKS, AND INFORMATION SYSTEMS (1973) (0)
- 236605 Advanced Topics Spring Semester, 2000 Today's Topics: Online Algorithm for Scheduling Jobs on Identical Machines. Online Algorithm for Scheduling Jobs on Uniformly Relateed Machines. Online Algorithm for Scheduling Jobs on Unrelated Machines. Randomized Online Algorithms 1 Online Algorithm fo (2007) (0)
- Efficient Allocation of Free Stuff Yossi Azar (2018) (0)
- Electronic markets with multiple submodular buyers (2019) (0)
- Session details: Session 5A (2002) (0)
- The Colored Ticket Algorithm. (1983) (0)
- COMPUTER USE: WHERE AND WHY (1973) (0)
- Fairness in Scheduling On-line Load Balancing with Applications to Machine Scheduling and Virtual Circuit Routing. In (1995) (0)
- 2008 Crm-fields-pims Prize Winner: Allan Borodin (2008) (0)
- Euclidean Embeddings that Preserve Volumes (0)
- COMPUTER USE: EXTENT AND GROWTH (1973) (0)
- VALUES, TECHNOLOGY, AND COMPUTERS (1973) (0)
- D S ] 2 1 A ug 2 02 0 GREEDY APPROACHES TO ONLINE STOCHASTIC MATCHING (2020) (0)
- Session details: Session 14B (2006) (0)
- Tribute to Roman Smolensky (1997) (0)
- Chapter 9 – COMPUTERS AND EMPLOYMENT1 (1973) (0)
- Session details: Session 8B (2006) (0)
- Competitive Paging with Locality of Reference (Brief Summary) (1991) (0)
- Prophet Matching in the Probe-Commit Model (2022) (0)
- Parallel (and other) extensions of the deterministic online model for bipartite matching and max-sat (2016) (0)
- Session details: Session 9A (2011) (0)
This paper list is powered by the following services:
Other Resources About Allan Borodin
What Schools Are Affiliated With Allan Borodin?
Allan Borodin is affiliated with the following schools:
