Nimrod Megiddo

According to our database, Nimrod Megiddo authored at least 125 papers between 1974 and 2023.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of two.

2023

An Efficient Interior-Point Method for Online Convex Optimization.

Elad Hazan, Nimrod Megiddo

CoRR, 2023

On "Indifference" and Backward Induction in Games with Perfect Information.

Nimrod Megiddo

CoRR, 2023

On the Use of Generative Models in Observational Causal Analysis.

Nimrod Megiddo

CoRR, 2023

Remarks on Utility in Repeated Bets.

Nimrod Megiddo

CoRR, 2023

2022

Bayesian Experimental Design for Symbolic Discovery.

Kenneth L. Clarkson, Cristina Cornelio, Sanjeeb Dash, Joao Goncalves, Lior Horesh, Nimrod Megiddo

CoRR, 2022

An Anomaly Detection Approach for Plankton Species Discovery.

Vito Paolo Pastore, Nimrod Megiddo, Simone Bianco

Proceedings of the Image Analysis and Processing - ICIAP 2022, 2022

2021

Integration of Data and Theory for Accelerated Derivable Symbolic Discovery.

Cristina Cornelio, Sanjeeb Dash, Vernon Austel, Tyler R. Josephson, Joao Goncalves, Kenneth L. Clarkson, Nimrod Megiddo, Bachir El Khadir, Lior Horesh

CoRR, 2021

2020

Symbolic Regression using Mixed-Integer Nonlinear Optimization.

Vernon Austel, Cristina Cornelio, Sanjeeb Dash, Joao Goncalves, Lior Horesh, Tyler R. Josephson, Nimrod Megiddo

CoRR, 2020

2019

Carving Perfect Layers out of Docker Images.

Dimitris Skourtis, Lukas Rupprecht, Vasily Tarasov, Nimrod Megiddo

Proceedings of the 11th USENIX Workshop on Hot Topics in Cloud Computing, 2019

2016

Strategic Classification.

Moritz Hardt, Nimrod Megiddo, Christos H. Papadimitriou, Mary Wootters

Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, 2016

Adaptive Caching in Big SQL using the HDFS Cache.

Avrilia Floratou, Nimrod Megiddo, Navneet Potti, Fatma Özcan, Uday Kale, Jan Schmitz-Hermes

Proceedings of the Seventh ACM Symposium on Cloud Computing, 2016

2014

Equilibrium Computation (Dagstuhl Seminar 14342).

Nimrod Megiddo, Kurt Mehlhorn, Rahul Savani, Vijay V. Vazirani

Dagstuhl Reports, 2014

Optimizing The Selection of Strangers To Answer Questions in Social Media.

Jalal Mahmud, Michelle X. Zhou, Nimrod Megiddo, Jeffrey Nichols, Clemens Drews

CoRR, 2014

2013

Recommending targeted strangers from whom to solicit information on social media.

Jalal Mahmud, Michelle X. Zhou, Nimrod Megiddo, Jeffrey Nichols, Clemens Drews

Proceedings of the 18th International Conference on Intelligent User Interfaces, 2013

2010

10171 Abstracts Collection - Equilibrium Computation.

Edith Elkind, Nimrod Megiddo, Peter Bro Miltersen, Bernhard von Stengel, Vijay V. Vazirani

Proceedings of the Equilibrium Computation, 25.04. - 30.04.2010, 2010

Formation of preferences and strategic analysis.

Nimrod Megiddo

Proceedings of the Behavioral and Quantitative Game Theory, 2010

2008

Efficient Coalition Detection in Traitor Tracing.

Hongxia Jin, Jeffery Lotspiech, Nimrod Megiddo

Proceedings of The IFIP TC-11 23rd International Information Security Conference, 2008

Adaptive traitor tracing for large anonymous attack.

Hongxia Jin, Jeffrey B. Lotspiech, Michael J. Nelson, Nimrod Megiddo

Proceedings of the 8th ACM Workshop on Digital Rights Management, 2008

Dynamic faceted search for discovery-driven analysis.

Debabrata Dash, Jun Rao, Nimrod Megiddo, Anastasia Ailamaki, Guy M. Lohman

Proceedings of the 17th ACM Conference on Information and Knowledge Management, 2008

2007

Consistent selectivity estimation via maximum entropy.

Volker Markl, Peter J. Haas, Marcel Kutsch, Nimrod Megiddo, Utkarsh Srivastava, Tam Minh Tran

VLDB J., 2007

Continuity Properties of Equilibrium Prices and Allocations in Linear Fisher Markets.

Nimrod Megiddo, Vijay V. Vazirani

Proceedings of the Internet and Network Economics, Third International Workshop, 2007

Online Learning with Prior Knowledge.

Elad Hazan, Nimrod Megiddo

Proceedings of the Learning Theory, 20th Annual Conference on Learning Theory, 2007

2006

Preface.

Nimrod Megiddo, Yinfeng Xu, Binhai Zhu

Theor. Comput. Sci., 2006

Combining expert advice in reactive environments.

Daniela Pucci de Farias, Nimrod Megiddo

J. ACM, 2006

MAXENT: consistent cardinality estimation in action.

Volker Markl, Marcel Kutsch, Tam Minh Tran, Peter J. Haas, Nimrod Megiddo

Proceedings of the ACM SIGMOD International Conference on Management of Data, 2006

Integrating a Maximum-Entropy Cardinality Estimator into DB2 UDB.

Marcel Kutsch, Peter J. Haas, Volker Markl, Nimrod Megiddo, Tam Minh Tran

Proceedings of the Advances in Database Technology, 2006

2005

Consistently Estimating the Selectivity of Conjuncts of Predicates.

Volker Markl, Nimrod Megiddo, Marcel Kutsch, Tam Minh Tran, Peter J. Haas, Utkarsh Srivastava

Proceedings of the 31st International Conference on Very Large Data Bases, Trondheim, Norway, August 30, 2005

2004

Linear programming.

Martin E. Dyer, Nimrod Megiddo, Emo Welzl

Proceedings of the Handbook of Discrete and Computational Geometry, Second Edition., 2004

Outperforming LRU with an Adaptive Replacement Cache Algorithm.

Nimrod Megiddo, Dharmendra S. Modha

Computer, 2004

Exploration-Exploitation Tradeoffs for Experts Algorithms in Reactive Environments.

Daniela Pucci de Farias, Nimrod Megiddo

Proceedings of the Advances in Neural Information Processing Systems 17 [Neural Information Processing Systems, 2004

2003

One Up on LRU.

Nimrod Megiddo, Dharmendra S. Modha

login Usenix Mag., 2003

How to Combine Expert (and Novice) Advice when Actions Impact the Environment?

Daniela Pucci de Farias, Nimrod Megiddo

Proceedings of the Advances in Neural Information Processing Systems 16 [Neural Information Processing Systems, 2003

ARC: A Self-Tuning, Low Overhead Replacement Cache.

Nimrod Megiddo, Dharmendra S. Modha

Proceedings of the FAST '03 Conference on File and Storage Technologies, March 31, 2003

2002

Automating physical database design in a parallel database.

Jun Rao, Chun Zhang, Nimrod Megiddo, Guy M. Lohman

Proceedings of the 2002 ACM SIGMOD International Conference on Management of Data, 2002

Attribute Classification Using Feature Analysis.

Felix Naumann, Ching-Tien Ho, Xuqing Tian, Laura M. Haas, Nimrod Megiddo

Proceedings of the 18th International Conference on Data Engineering, San Jose, CA, USA, February 26, 2002

2001

Improved Algorithms and Analysis for Secretary Problems and Generalizations.

Miklós Ajtai, Nimrod Megiddo, Orli Waarts

SIAM J. Discret. Math., 2001

An Improved Predictive Accuracy Bound for Averaging Classifiers.

John Langford, Matthias W. Seeger, Nimrod Megiddo

Proceedings of the Eighteenth International Conference on Machine Learning (ICML 2001), Williams College, Williamstown, MA, USA, June 28, 2001

2000

A sublinear parallel algorithm for stable matching.

Tomás Feder, Nimrod Megiddo, Serge A. Plotkin

Theor. Comput. Sci., 2000

An analytical model for loop tiling and its solution.

Vivek Sarkar, Nimrod Megiddo

Proceedings of the 2000 IEEE International Symposium on Performance Analysis of Systems and Software, 2000

1999

Fast indexing method for multidimensional nearest-neighbor search.

John A. Shepherd, Xiaoming Zhu, Nimrod Megiddo

Proceedings of the Storage and Retrieval for Image and Video Databases VII, 1999

1998

Using Fast Matrix Multiplication to Find Basic Solutions.

Peter A. Beling, Nimrod Megiddo

Theor. Comput. Sci., 1998

A modified layered-step interior-point algorithm for linear programming.

Nimrod Megiddo, Shinji Mizuno, Takashi Tsuchiya

Math. Program., 1998

Discovering Predictive Association Rules.

Nimrod Megiddo, Ramakrishnan Srikant

Proceedings of the Fourth International Conference on Knowledge Discovery and Data Mining (KDD-98), 1998

Discovery-Driven Exploration of OLAP Data Cubes.

Sunita Sarawagi, Rakesh Agrawal, Nimrod Megiddo

Proceedings of the Advances in Database Technology, 1998

1997

Optimal Weighted Loop Fusion for Parallel Programs.

Nimrod Megiddo, Vivek Sarkar

Proceedings of the 9th Annual ACM Symposium on Parallel Algorithms and Architectures, 1997

Range Queries in OLAP Data Cubes.

Ching-Tien Ho, Rakesh Agrawal, Nimrod Megiddo, Ramakrishnan Srikant

Proceedings of the SIGMOD 1997, 1997

1996

A Deterministic Poly(log log N)-Time N-Processor Algorithm for Linear Programming in Fixed Dimensions.

Miklós Ajtai, Nimrod Megiddo

SIAM J. Comput., 1996

A Linear Programming Instance with Many Crossover Events.

Shinji Mizuno, Nimrod Megiddo, Takashi Tsuchiya

J. Complex., 1996

on the Geometric Separability of Boolean Functions.

Tibor Hegedüs, Nimrod Megiddo

Discret. Appl. Math., 1996

Segmenting and representing background in color images.

Qian Huang, Byron Dom, Nimrod Megiddo, Wayne Niblack

Proceedings of the 13th International Conference on Pattern Recognition, 1996

Color image background segmentation and representation.

Qian Huang, Nimrod Megiddo

Proceedings of the Proceedings 1996 International Conference on Image Processing, 1996

1994

Constructing Small Sample Spaces Satisfying Given Constraints.

Daphne Koller, Nimrod Megiddo

SIAM J. Discret. Math., 1994

Improved Algorithms for Linear Inequalities With Two Variables per Inequality.

Edith Cohen, Nimrod Megiddo

SIAM J. Comput., 1994

New algorithms for generalized network flows.

Edith Cohen, Nimrod Megiddo

Math. Program., 1994

Parallel Linear Programming in Fixed Dimension Almost Surely in Constant Time.

Noga Alon, Nimrod Megiddo

J. ACM, 1994

Algorithms and Complexity Analysis for Some Flow Problems.

Edith Cohen, Nimrod Megiddo

Algorithmica, 1994

Fast algorithms for finding randomized strategies in game trees.

Daphne Koller, Nimrod Megiddo, Bernhard von Stengel

Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 1994

On Probabilistic Machines, Bounded Rationality and Average-Case Complexity.

Nimrod Megiddo

Proceedings of the Essays in Game Theory, In Honor of Michael Maschler, 1994

1993

Linear time algorithms for some separable quadratic programming problems.

Nimrod Megiddo, Arie Tamir

Oper. Res. Lett., 1993

A primal-dual infeasible-interior-point algorithm for linear programming.

Masakazu Kojima, Nimrod Megiddo, Shinji Mizuno

Math. Program., 1993

Theoretical convergence of large-step primal-dual interior point algorithms for linear programming.

Masakazu Kojima, Nimrod Megiddo, Shinji Mizuno

Math. Program., 1993

Tight bounds and 2-approximation algorithms for integer programs with two variables per inequality.

Dorit S. Hochbaum, Nimrod Megiddo, Joseph Naor, Arie Tamir

Math. Program., 1993

A General Framework of Continuation Methods for Complementarity Problems.

Masakazu Kojima, Nimrod Megiddo, Shinji Mizuno

Math. Oper. Res., 1993

Strongly Polynomial-Time and NC Algorithms for Detecting Cycles in Periodic Graphs.

Edith Cohen, Nimrod Megiddo

J. ACM, 1993

The Minimum Reservation Rate Problem in Digital Audio/Video Systems.

Nimrod Megiddo, Moni Naor, David P. Anderson

Proceedings of the Second Israel Symposium on Theory of Computing Systems, 1993

1992

An interior point potential reduction algorithm for the linear complementarity problem.

Masakazu Kojima, Nimrod Megiddo, Yinyu Ye

Math. Program., 1992

A Note on Approximate Linear Programming.

Nimrod Megiddo

Inf. Process. Lett., 1992

A Deterministic Poly(log log N)-Time N-Processor Algorithm for Linear Programming in Fixed Dimension

Miklós Ajtai, Nimrod Megiddo

Proceedings of the 24th Annual ACM Symposium on Theory of Computing, 1992

1991

On Total Functions, Existence Theorems and Computational Complexity.

Nimrod Megiddo, Christos H. Papadimitriou

Theor. Comput. Sci., 1991

A unified approach to interior point algorithms for linear complementarity problems: A summary.

Masakazu Kojima, Nimrod Megiddo, Toshihito Noma, Akiko Yoshise

Oper. Res. Lett., 1991

Homotopy Continuation Methods for Nonlinear Complementarity Problems.

Masakazu Kojima, Nimrod Megiddo, Toshihito Noma

Math. Oper. Res., 1991

Exact Computation of Optimal Inventory Policies Over an Unbounded Horizon.

Refael Hassin, Nimrod Megiddo

Math. Oper. Res., 1991

On Finding Primal- and Dual-Optimal Bases.

Nimrod Megiddo

INFORMS J. Comput., 1991

Approximation algorithms for hitting objects with straight lines.

Refael Hassin, Nimrod Megiddo

Discret. Appl. Math., 1991

Improved Algorithms for Linear Inequalities with Two Variables per Inequality (Extended Abstract)

Edith Cohen, Nimrod Megiddo

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

A Unified Approach to Interior Point Algorithms for Linear Complementarity Problems

Masakazu Kojima, Nimrod Megiddo, Toshihito Noma, Akiko Yoshise

Lecture Notes in Computer Science 538, Springer, ISBN: 3-540-54509-3, 1991

1990

Linear Programming with Two Variables per Inequality in Poly-Log Time.

George S. Lueker, Nimrod Megiddo, Vijaya Ramachandran

SIAM J. Comput., 1990

On the Complexity of Some Geometric Problems in Unbounded Dimension.

Nimrod Megiddo

J. Symb. Comput., 1990

A Logic for Reasoning about Probabilities

Ronald Fagin, Joseph Y. Halpern, Nimrod Megiddo

Inf. Comput., 1990

Recognizing Properties of Periodic Graphs.

Edith Cohen, Nimrod Megiddo

Proceedings of the Applied Geometry And Discrete Mathematics, 1990

1989

Boundary Behavior of Interior Point Algorithms in Linear Programming.

Nimrod Megiddo, Michael Shub

Math. Oper. Res., 1989

On the Ball Spanned by Balls.

Nimrod Megiddo

Discret. Comput. Geom., 1989

Extending NC and RNC Algorithms.

Nimrod Megiddo

Algorithmica, 1989

Strongly Polynomial-Time and NC Algorithms for Detecting Cycles in Dynamic Graphs (Preliminary Version)

Edith Cohen, Nimrod Megiddo

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

1988

On Finding a Minimum Dominating Set in a Tournament.

Nimrod Megiddo, Uzi Vishkin

Theor. Comput. Sci., 1988

The complexity of searching a graph.

Nimrod Megiddo, S. Louis Hakimi, M. R. Garey, David S. Johnson, Christos H. Papadimitriou

J. ACM, 1988

On the Complexity of Polyhedral Separability.

Nimrod Megiddo

Discret. Comput. Geom., 1988

1986

A note on degeneracy in linear programming.

Nimrod Megiddo

Math. Program., 1986

On the expected number of linear complementarity cones intersected by random and semi-random rays.

Nimrod Megiddo

Math. Program., 1986

Improved asymptotic analysis of the average number of steps performed by the self-dual simplex algorithm.

Nimrod Megiddo

Math. Program., 1986

An O(n log n) Randomizing Algorithm for the Weighted Euclidean 1-Center Problem.

Nimrod Megiddo, Eitan Zemel

J. Algorithms, 1986

Introduction: New Approaches to Linear Programming.

Nimrod Megiddo

Algorithmica, 1986

On Play by Means of Computing Machines.

Nimrod Megiddo, Avi Wigderson

Proceedings of the 1st Conference on Theoretical Aspects of Reasoning about Knowledge, 1986

Linear Programming with Two Variables per Inequality in Poly-Log Time (Preliminary Version)

George S. Lueker, Nimrod Megiddo, Vijaya Ramachandran

Proceedings of the 18th Annual ACM Symposium on Theory of Computing, 1986

1985

A Simplex Algorithm Whose Average Number of Steps Is Bounded between Two Quadratic Functions of the Smaller Dimension

Ilan Adler, Nimrod Megiddo

J. ACM, October, 1985

A Two-Resource Allocation Problem Solvable in Linear Time.

Nimrod Megiddo, Tetsuo Ichimori

Math. Oper. Res., 1985

Optimal precision in the presence of uncertainty.

Joseph Y. Halpern, Nimrod Megiddo, Ashfaq A. Munshi

J. Complex., 1985

Partitioning with Two Lines in the Plane.

Nimrod Megiddo

J. Algorithms, 1985

An Optimal Algorithm for Finding all the Jumps of a Monotone Step-Function.

Refael Hassin, Nimrod Megiddo

J. Algorithms, 1985

Optimal Precision in the Presence of Uncertainty (Preliminary Version)

Joseph Y. Halpern, Nimrod Megiddo, Ashfaq A. Munshi

Proceedings of the 17th Annual ACM Symposium on Theory of Computing, 1985

1984

On the Complexity of Some Common Geometric Location Problems.

Nimrod Megiddo, Kenneth J. Supowit

SIAM J. Comput., 1984

Linear Programming in Linear Time When the Dimension Is Fixed.

Nimrod Megiddo

J. ACM, 1984

1983

Applying Parallel Computation Algorithms in the Design of Serial Algorithms

Nimrod Megiddo

J. ACM, October, 1983

New Results on the Complexity of p-Center Problems.

Nimrod Megiddo, Arie Tamir

SIAM J. Comput., 1983

Linear-Time Algorithms for Linear Programming in R³ and Related Problems.

Nimrod Megiddo

SIAM J. Comput., 1983

Towards a Genuinely Polynomial Algorithm for Linear Programming.

Nimrod Megiddo

SIAM J. Comput., 1983

The Weighted Euclidean 1-Center Problem.

Nimrod Megiddo

Math. Oper. Res., 1983

1982

Is Binary Encoding Appropriate for the Problem-Language Relationship?

Nimrod Megiddo

Theor. Comput. Sci., 1982

On the complexity of locating linear facilities in the plane.

Nimrod Megiddo, Arie Tamir

Oper. Res. Lett., 1982

On the complexity of the one-terminal network design problem.

Nimrod Megiddo

Oper. Res. Lett., 1982

Linear-Time Algorithms for Linear Programming in R^3 and Related Problems

Nimrod Megiddo

Proceedings of the 23rd Annual Symposium on Foundations of Computer Science, 1982

1981

An O(n log² n) Algorithm for the k-th Longest Path in a Tree with Applications to Location Problems.

Nimrod Megiddo, Arie Tamir, Eitan Zemel, R. Chandrasekaran

SIAM J. Comput., 1981

The Complexity of Searching a Graph (Preliminary Version)

Nimrod Megiddo, S. Louis Hakimi, M. R. Garey, David S. Johnson, Christos H. Papadimitriou

Proceedings of the 22nd Annual Symposium on Foundations of Computer Science, 1981

1979

On Fulkerson's Conjecture About Consistent Labeling Processes.

Nimrod Megiddo, Zvi Galil

Math. Oper. Res., 1979

Combinatorial Optimization with Rational Objective Functions.

Nimrod Megiddo

Math. Oper. Res., 1979

A Fast Selection Algorithm and the Problem of Optimum Distribution of Effort.

Zvi Galil, Nimrod Megiddo

J. ACM, 1979

1978

An O(N log N) Algorithm for a Class of Matching Problems.

Nimrod Megiddo, Arie Tamir

SIAM J. Comput., 1978

Cost allocation for steiner trees.

Nimrod Megiddo

Networks, 1978

Computational Complexity of the Game Theory Approach to Cost Allocation for a Tree.

Nimrod Megiddo

Math. Oper. Res., 1978

1977

Cyclic Ordering is NP-Complete.

Zvi Galil, Nimrod Megiddo

Theor. Comput. Sci., 1977

On the existence and uniqueness of solutions in nonlinear complementarity theory.

Nimrod Megiddo, Masakazu Kojima

Math. Program., 1977

A monotone complementarity problem with feasible solutions but no complementary solutions.

Nimrod Megiddo

Math. Program., 1977

On monotonicity in parametric linear complementarity problems.

Nimrod Megiddo

Math. Program., 1977

Mixtures of order matrices and generalized order matrices.

Nimrod Megiddo

Discret. Math., 1977

1974

Optimal flows in networks with multiple sources and sinks.

Nimrod Megiddo

Math. Program., 1974