Allan Borodin

CoRR, 2024

Primarily about primaries.

[BibT_eX]

[DOI]

Artif. Intell., 2024

2023

Online Bipartite Matching in the Probe-Commit Model.

[BibT_eX]

[DOI]

CoRR, 2023

Any-Order Online Interval Selection.

[BibT_eX]

[DOI]

Proceedings of the Approximation and Online Algorithms - 21st International Workshop, 2023

A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation.

[BibT_eX]

[DOI]

Proceedings of the Logic, 2023

2022

Distortion in Voting with Top-t Preferences.

[BibT_eX]

[DOI]

Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, 2022

Little House (Seat) on the Prairie: Compactness, Gerrymandering, and Population Distribution.

[BibT_eX]

[DOI]

Proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems, 2022

Prophet Matching in the Probe-Commit Model.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2022

2021

Prophet Inequality Matching Meets Probing with Commitment.

[BibT_eX]

[DOI]

CoRR, 2021

Secretary Matching Meets Probing with Commitment.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2021

2020

Advice Complexity of Priority Algorithms.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2020

An Experimental Study of Algorithms for Online Bipartite Matching.

[BibT_eX]

[DOI]

ACM J. Exp. Algorithmics, 2020

Greedy Approaches to Online Stochastic Matching.

[BibT_eX]

[DOI]

CoRR, 2020

Bipartite Stochastic Matching: Online, Random Order, and I.I.D. Models.

[BibT_eX]

[DOI]

CoRR, 2020

2019

On extensions of the deterministic online model for bipartite matching and max-sat.

[BibT_eX]

[DOI]

Nicolas Pena

Theor. Comput. Sci., 2019

On Conceptually Simple Algorithms for Variants of Online Bipartite Matching.

[BibT_eX]

[DOI]

Amirali Salehi-Abari

Theory Comput. Syst., 2019

Electronic markets with multiple submodular buyers.

[BibT_eX]

[DOI]

CoRR, 2019

Efficient Allocation of Free Stuff.

[BibT_eX]

[DOI]

Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems, 2019

2018

A Simple PTAS for the Dual Bin Packing Problem and Advice Complexity of Its Online Version.

[BibT_eX]

[DOI]

Amirali Salehi-Abari

Proceedings of the 1st Symposium on Simplicity in Algorithms, 2018

Big City vs. the Great Outdoors: Voter Distribution and How It Affects Gerrymandering.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, 2018

Seasonal Goods and Spoiled Milk: Pricing for a Limited Shelf-Life.

[BibT_eX]

[DOI]

Atiyeh Ashari Ghomi

Omer Lev

Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems, 2018

Greedy Bipartite Matching in Random Type Poisson Arrival Model.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2018

2017

Sequential Posted-Price Mechanisms with Correlated Valuations.

[BibT_eX]

[DOI]

ACM Trans. Economics and Comput., 2017

Max-Sum Diversification, Monotone Submodular Functions, and Dynamic Updates.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2017

Equilibria of Greedy Combinatorial Auctions.

[BibT_eX]

[DOI]

Brendan Lucier

SIAM J. Comput., 2017

Strategyproof Mechanisms for Competitive Influence in Networks.

[BibT_eX]

[DOI]

Algorithmica, 2017

2016

On the Limitations of Greedy Mechanism Design for Truthful Combinatorial Auctions.

[BibT_eX]

[DOI]

Brendan Lucier

ACM Trans. Economics and Comput., 2016

On the limitations of deterministic de-randomizations for online bipartite matching and max-sat.

[BibT_eX]

[DOI]

Nicolas Pena

CoRR, 2016

Budgetary Effects on Pricing Equilibrium in Online Markets.

[BibT_eX]

[DOI]

Omer Lev

Tyrone Strangway

Proceedings of the 2016 International Conference on Autonomous Agents & Multiagent Systems, 2016

2014

Weakly Submodular Functions.

[BibT_eX]

[DOI]

Dai Le

CoRR, 2014

Bounds on Double-Sided Myopic Algorithms for Unconstrained Non-monotoneSubmodular Maximization.

[BibT_eX]

[DOI]

Norman Huang

Proceedings of the Algorithms and Computation - 25th International Symposium, 2014

2013

Bounds on Double-Sided Myopic Algorithms for Unconstrained Non-monotone Submodular Maximization.

[BibT_eX]

[DOI]

Norman Huang

CoRR, 2013

Computing (and Life) Is All about Tradeoffs - A Small Sample of Some Computational Tradeoffs.

[BibT_eX]

[DOI]

Proceedings of the Space-Efficient Data Structures, 2013

2012

On sum coloring and sum multi-coloring for restricted families of graphs.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2012

Elimination graphs.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2012

Truthful Mechanisms for Competing Submodular Processes

[BibT_eX]

[DOI]

CoRR, 2012

Max-Sum diversification, monotone submodular functions and dynamic updates.

[BibT_eX]

[DOI]

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?

[BibT_eX]

[DOI]

David Cashman

Avner Magen

ACM Trans. Algorithms, 2011

Special Issue In Memory of Misha Alekhnovich. Foreword.

[BibT_eX]

[DOI]

Toniann Pitassi

Alexander A. Razborov

Comput. Complex., 2011

Toward a Model for Backtracking and Dynamic Programming.

[BibT_eX]

[DOI]

Michael Alekhnovich

Joshua Buresh-Oppenheim

Russell Impagliazzo

Avner Magen

Toniann Pitassi

Comput. Complex., 2011

2010

Priority algorithms for graph optimization problems.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2010

Randomized priority algorithms.

[BibT_eX]

[DOI]

Spyros Angelopoulos

Theor. Comput. Sci., 2010

Threshold Models for Competitive Influence in Social Networks.

[BibT_eX]

[DOI]

Yuval Filmus

Joel Oren

Proceedings of the Internet and Network Economics - 6th International Workshop, 2010

Price of Anarchy for Greedy Auctions.

[BibT_eX]

[DOI]

Brendan Lucier

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.

[BibT_eX]

[DOI]

Proceedings of the Theory and Applications of Satisfiability Testing, 2010

2009

Criteria for Cluster-Based Personalized Search.

[BibT_eX]

[DOI]

Internet Math., 2009

Toward a Model for Backtracking and Dynamic Programming.

[BibT_eX]

[DOI]

Michael Alekhnovich

Joshua Buresh-Oppenheim

Russell Impagliazzo

Avner Magen

Electron. Colloquium Comput. Complex., 2009

Cluster Based Personalized Search.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Models for the Web-Graph, 6th International Workshop, 2009

Invited Talk II The Power and Limitations of Simple Algorithms: A Partial Case Study of Greedy Mechanisim Design for Combinatorial Actions.

[BibT_eX]

[DOI]

Proceedings of the Algorithmic Aspects of Wireless Sensor Networks, 2009

2008

Priority algorithms for the subset-sum problem.

[BibT_eX]

[DOI]

J. Comb. Optim., 2008

Extracting and ranking viral communities using seeds and content similarity.

[BibT_eX]

[DOI]

Leslie Goldsmith

Proceedings of the HYPERTEXT 2008, 2008

2006

Further Reflections on a Theory for Basic Algorithms.

[BibT_eX]

[DOI]

Proceedings of the Algorithmic Aspects in Information and Management, 2006

2005

Link analysis ranking: algorithms, theory, and experiments.

[BibT_eX]

[DOI]

ACM Trans. Internet Techn., 2005

Towards a Theory of Algorithms.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Data Structures, 9th International Workshop, 2005

2004

Subquadratic Approximation Algorithms for Clustering Problems in High Dimensional Spaces.

[BibT_eX]

[DOI]

Rafail Ostrovsky

Mach. Learn., 2004

Stability Preserving Transformations: Packet Routing Networks with Edge Capacities and Speeds.

[BibT_eX]

[DOI]

Rafail Ostrovsky

J. Interconnect. Networks, 2004

Can We Learn to Beat the Best Stock.

[BibT_eX]

[DOI]

Vincent Gogan

J. Artif. Intell. Res., 2004

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

[BibT_eX]

[DOI]

Spyros Angelopoulos

Algorithmica, 2004

Priority Algorithms for Graph Optimization Problems.

[BibT_eX]

[DOI]

Joan Boyar

Kim S. Larsen

Proceedings of the Approximation and Online Algorithms, Second International Workshop, 2004

2003

(Incremental) Priority Algorithms.

[BibT_eX]

[DOI]

Morten N. Nielsen

Charles Rackoff

Algorithmica, 2003

Perturbation of the Hyper-Linked Environment.

[BibT_eX]

[DOI]

Proceedings of the Computing and Combinatorics, 9th Annual International Conference, 2003

2001

Adversarial queuing theory.

[BibT_eX]

[DOI]

J. ACM, 2001

Finding authorities and hubs from link structures on the World Wide Web.

[BibT_eX]

[DOI]

Proceedings of the Tenth International World Wide Web Conference, 2001

2000

On the Competitive Theory and Practice of Portfolio Selection (Extended Abstract).

[BibT_eX]

[DOI]

Vincent Gogan

Proceedings of the LATIN 2000: Theoretical Informatics, 2000

1999

A Time-Space Tradeoff for Undirected Graph Traversal by Walking Automata.

[BibT_eX]

[DOI]

SIAM J. Comput., 1999

On Randomization in On-Line Computation.

[BibT_eX]

[DOI]

Inf. Comput., 1999

Lower Bounds for High Dimensional Nearest Neighbor Search and Related Problems.

[BibT_eX]

[DOI]

Rafail Ostrovsky

Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

1998

Online computation and competitive analysis.

[BibT_eX]

Cambridge University Press, ISBN: 978-0-521-56392-5, 1998

1997

Deterministic Many-to-Many Hot Potato Routing.

[BibT_eX]

[DOI]

Baruch Schieber

IEEE Trans. Parallel Distributed Syst., 1997

How much can hardware help routing?

[BibT_eX]

[DOI]

J. ACM, 1997

Tribute to Roman Smolensky.

[BibT_eX]

[DOI]

Comput. Complex., 1997

On Ranomization in Online Computation.

[BibT_eX]

[DOI]

Proceedings of the Twelfth Annual IEEE Conference on Computational Complexity, 1997

1996

Time-Space Tradeoffs for Undirected Graph Traversal by Graph Automata.

[BibT_eX]

[DOI]

Inf. Comput., 1996

Adversarial Queueing Theory.

[BibT_eX]

[DOI]

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

1995

Competitive Paging with Locality of Reference.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1995

1994

On the Power of Randomization in On-Line Algorithms.

[BibT_eX]

[DOI]

Algorithmica, 1994

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

[BibT_eX]

[DOI]

Shai Ben-David

Algorithmica, 1994

1993

On Lower Bounds for Read-K-Times Branching Programs.

[BibT_eX]

[DOI]

Alexander A. Razborov

Roman Smolensky

Comput. Complex., 1993

Towards a Better Understanding of the Pure Packet Routing.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Data Structures, Third Workshop, 1993

Time Space Tradeoffs (Getting Closer to the Barrier?).

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Computation, 4th International Symposium, 1993

1992

Lower Bounds on the Length of Universal Traversal Sequences.

[BibT_eX]

[DOI]

Walter L. Ruzzo

Martin Tompa

J. Comput. Syst. Sci., 1992

An Optimal On-Line Algorithm for Metrical Task System.

[BibT_eX]

[DOI]

Nathan Linial

Michael E. Saks

J. ACM, 1992

Can competitive analysis be made competitive?

[BibT_eX]

[DOI]

Proceedings of the 1992 Conference of the Centre for Advanced Studies on Collaborative Research, 1992

1991

On the Decidability of Sparse Univariate Polynomial Interpolation.

[BibT_eX]

[DOI]

Prasoon Tiwari

Comput. Complex., 1991

Competitive Paging with Locality of Reference (Preliminary Version)

[BibT_eX]

[DOI]

Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, 1991

Competitive Paging with Locality of Reference (Brief Summary).

[BibT_eX]

[DOI]

Proceedings of the On-Line Algorithms, 1991

1990

On the Decidability of Sparse Univariate Polynomial Interpolation (Preliminary Version)

[BibT_eX]

[DOI]

Prasoon Tiwari

Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, 1990

On the Power of Randomization in Online Algorithms (Extended Abstract)

[BibT_eX]

[DOI]

Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, 1990

Time-Space Tradeoffs for Undirected Graph Traversal

[BibT_eX]

[DOI]

Proceedings of the 31st Annual Symposium on Foundations of Computer Science, 1990

1989

Distributed FIFO Allocation of Identical Resources Using Small Shared Space.

[BibT_eX]

[DOI]

ACM Trans. Program. Lang. Syst., 1989

Erratum: Two Applications of Inductive Counting for Complementation Problems.

[BibT_eX]

[DOI]

SIAM J. Comput., 1989

Two Applications of Inductive Counting for Complementation Problems.

[BibT_eX]

[DOI]

SIAM J. Comput., 1989

Bounds on Universal Sequences.

[BibT_eX]

[DOI]

SIAM J. Comput., 1989

Lower Bounds on the Length of Universal Traversal Sequences (Detailed Abstract)

[BibT_eX]

[DOI]

Walter L. Ruzzo

Martin Tompa

Proceedings of the 21st Annual ACM Symposium on Theory of Computing, 1989

1988

A Tradeoff Between Search and Update Time for the Implicit Dictionary Problem.

[BibT_eX]

[DOI]

Friedhelm Meyer auf der Heide

Faith E. Fich

Eli Upfal

Avi Wigderson

Theor. Comput. Sci., 1988

Two applications of complementation via inductive counting.

[BibT_eX]

[DOI]

Proceedings of the Proceedings: Third Annual Structure in Complexity Theory Conference, 1988

Juris Hartmanis: building a department-building a discipline.

[BibT_eX]

[DOI]

Proceedings of the Proceedings: Third Annual Structure in Complexity Theory Conference, 1988

1987

A Time-Space Tradeoff for Element Distinctness.

[BibT_eX]

[DOI]

Friedhelm Meyer auf der Heide

Faith E. Fich

Eli Upfal

Avi Wigderson

SIAM J. Comput., 1987

An Optimal Online Algorithm for Metrical Task Systems

[BibT_eX]

[DOI]

Nathan Linial

Michael E. Saks

Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987

1986

Bounds for Width Two Branching Programs.

[BibT_eX]

[DOI]

SIAM J. Comput., 1986

1985

Decreasing the Nesting Depth of Expressions Involving Square Roots.

[BibT_eX]

[DOI]

J. Symb. Comput., 1985

Routing, Merging, and Sorting on Parallel Models of Computation.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1985

1983

Parallel Computation for Well-Endowed Rings and Space-Bounded Probabilistic Machines

[BibT_eX]

[DOI]

Nicholas Pippenger

Inf. Control., 1983

1982

Fast Parallel Matrix and GCD Computations

[BibT_eX]

[DOI]

Joachim von zur Gathen

Inf. Control., March, 1982

A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation.

[BibT_eX]

[DOI]

SIAM J. Comput., 1982

Routing, Merging and Sorting on Parallel Models of Computation (Extended Abstract)

[BibT_eX]

[DOI]

Proceedings of the 14th Annual ACM Symposium on Theory of Computing, 1982

1981

A Time-Space Tradeoff for Sorting on Non-Oblivious Machines.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1981

Efficient Searching Using Partial Ordering.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1981

1979

A time-space tradeoff for sorting and related non-oblivious computations.

[BibT_eX]

[DOI]

SIGACT News, 1979

Resource Allocation with Immunity to Limited Process Failure (Preliminary Report)

[BibT_eX]

[DOI]

Proceedings of the 20th Annual Symposium on Foundations of Computer Science, 1979

1977

On Relating Time and Space to Size and Depth.

[BibT_eX]

[DOI]

SIAM J. Comput., 1977

1976

On the Number of Additions to Compute Specific Polynomials.

[BibT_eX]

[DOI]

SIAM J. Comput., 1976

1975

The computational complexity of algebraic and numeric problems.

[BibT_eX]

[DOI]

J. Ian Munro

Elsevier computer science library 1, Elsevier, ISBN: 0444001565, 1975

1974

Social issues in computing: the course.

[BibT_eX]

[DOI]

C. C. Gotlieb

SIGCAS Comput. Soc., 1974

Fast Modular Transforms.

[BibT_eX]

[DOI]

R. Moenck

J. Comput. Syst. Sci., 1974

On the Number of Additions to Compute Specific Polynomials (Preliminary Version)

[BibT_eX]

[DOI]

Proceedings of the 6th Annual ACM Symposium on Theory of Computing, April 30, 1974

1972

Efficient Evaluation of Polynomial Forms.

[BibT_eX]

[DOI]

J. Ian Munro

J. Comput. Syst. Sci., 1972

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

[BibT_eX]

[DOI]

Robert L. Constable

J. ACM, 1972

Corrigendum: "Computational Complexity and the Existence of Complexity Gaps".

[BibT_eX]

[DOI]

J. ACM, 1972

Computational Complexity and the Existence of Complexity Gaps.

[BibT_eX]

[DOI]

J. ACM, 1972

Computers and Employment.

[BibT_eX]

[DOI]

C. C. Gotlieb

Commun. ACM, 1972

Fast Modular Transforms via Division

[BibT_eX]

[DOI]

R. Moenck

Proceedings of the 13th Annual Symposium on Switching and Automata Theory, 1972

1971

Evaluating Polynomials at Many Points.

[BibT_eX]

[DOI]

J. Ian Munro

Inf. Process. Lett., 1971

1970

On the Efficiency of Programs in Subrecursive Formalisms (Incomplete Version, Extended Abstract)

[BibT_eX]

[DOI]

Robert L. Constable

Proceedings of the 11th Annual Symposium on Switching and Automata Theory, 1970

1969

Computational Complexity and the Existence of Complexity Gaps.

[BibT_eX]

PhD thesis, 1969

Complexity Classes of Recursive Functions and the Existence of Complexity Gaps

[BibT_eX]

Proceedings of the 1st Annual ACM Symposium on Theory of Computing, 1969

Dense and Non-Dense Families of Complexity Classes

[BibT_eX]

[DOI]

Robert L. Constable