- Degrees
- Awards
- Institutions where I held visiting positions
- Memberships in Editorial Boards
- Grants and Research Contracts
- Publications: Journal Articles, Chapters in books and papers in proceedings, Technical Reports
- Patents

(all from The Hebrew University of Jerusalem, Israel):

- B.Sc., Mathematics, Physics and Complementary Studies
- M.Sc., Mathematics
- Ph.D.,
Mathematics

- The Joseph Levy Prize, ORSIS - Operations Research Society of Israel, 1986.
- ICS Prize, INFORMS Computing Society, 1992.
- Outstanding Innovation Award, IBM Corp., 1992.
- Frederick W. Lanchester Prize, INFORMS - Institute for Operations Research and the Management Sciences (formerly the Operations Research Society of America), 1992.

- Outstanding Innovation Award, IBM Corp., 1995.
- Pat Goldberg Memorial Best Paper Award, 2003.
- Outstanding Innovation Award, IBM Corp., 2004.
- Pat Goldberg Memorial Best Paper Award, 2005.
- INFORMS
Fellow Award, 2009.
- Society for the Advancement of Economic Theory Fellow Award, 2011.
- USENIX File and Storage Technologies (FAST) Test of Time Award , 2014.
- John von Neumann Theory Prize, INFORMS - Institute for Operations Research and the Management Sciences, 2014. (See the press release).

- Patent Portfolio Award, IBM Corp., 2015 (given to inventors whose patents are of significant value to IBM)
- Patent Income Award, IBM Corp., 2016.
- Outstanding Technical Achievement Award, IBM Corp., 2016

- Tokyo Institute of Technology
- University of Illinois at Urbana-Champaign, College of Commerce and Business Administration,
- Northwestern University, Kellogg Graduate School of Management,
- National Research Institute for Mathematical Sciences, C.S.I.R., South Africa
- Carnegie-Mellon University, Graduate School of Industrial Administration,
- Stanford University, Computer Science Department,
- Xerox Corp., PARC (Palo Alto Research Center)
- MSRI (Mathematical Sciences Research Institute), Berkeley, California
- Stanford University, Department of Management Science & Engineering

*Mathematics of Operations Research*:- Advisory Editor, 2010 - 2015.
- Editor-in-Chief, 2004 - 2009.
- Area Editor for Machine Learning, 2004 - 2010.
- Area Editor for Game Theory, 1999 - 2003.
- Associate Editor, 1983 - 1992.
*Discrete Optimization:*

o Editor-in-Chief, 2007 to date

o Member of the Editorial Board, 2004 - 2007.

*Journal of the ACM*: Area Editor for Operations Research, Game Theory, and Economics, 1988 - 2012.*Operations Research Letters:*

*Algorithmica*Member of the Editorial Board, 1985 - to date.: Associate Editor, 1986 - to date.Mathematical Programming: *Discrete Applied Mathematics*: Member ofthe Editorial Board, 1987 -to date. *Games and Economic Behavior*: Member of the Editorial Board, 1988 - 2012.*Journal of Combinatorial Optimization*: Member of the Editorial Board, 1995 - to date.*SIAM Journal on Discrete Mathematics*: Member of Editorial Board, 1987 - 1993.

- Studies in Locations, Allocations and Placements, NSF - National Science Foundation, 1982 - 1984.
- Linear Programming and Related Problems in Lower Dimensional Spaces, NSF - National Science Foundation, 1983 - 1985.
- Analysis of Solution Paths in Linear Programming and Extensions, ONR - Office of Naval Research, 1987 - 1990.
- Studies on the Complexity of Linear Programming and Related Topics, ONR - Office of Naval Research, 1991 - 1993.
- Topics
in Linear Programming and Related Problems, ONR - Office of Naval Research, 1994 -
1997.

- N.
Megiddo,
(edited), Springer-Verlag, New York, 1994.Essays in Game Theory in Honor of Michael Maschler - M.
Kojima, N. Megiddo, T. Noma and A. Yoshise, "
*A unified approach to interior point algorithms for linear complementarity problems*," Lecture Notes in Computer Science**538**, Springer-Verlag, 1991. - N.
Megiddo,
(edited), Springer-Verlag, New York, 1988.Progress in Mathematical Programming: Interior-Point and Related Methods - N. Megiddo, Y. Xu, and B. Zhu, Algorithmic Applications in Management, First International Conference, AAIM 2005, Xian, China, June 22-25, 2005, Proceedings Springer 2005.
**Books in Hebrew**

1.
N.
Megiddo, "The
kernel and the nucleolus of a product of simple games," *Israel
Journal of Mathematics* **9** (1971), No. 9, 210-221.

2.
N.
Megiddo, "Nucleoluses of
compound simple games," *SIAM Journal on Applied Mathematics*
**26** (1974), No. 3, 607-621.

3.
N.
Megiddo, "Kernels
of compound games with simple components," *Pacific Journal of
Mathematics* **50** (1974), No. 2, 531-555.

4.
N.
Megiddo, "On
the nonmonotonicity of the bargaining set, the kernel
and the nucleolus of a game," *SIAM Journal on Applied Mathematics*
**27** (1974), No. 2, 355-358.

5.
N.
Megiddo, "Optimal
flows in networks with multiple sources and sinks," *Mathematical
Programming* **7** (1974), No. 3, 97-107.

6.
N.
Megiddo, "Tensor
decomposition of cooperative games," *SIAM Journal on Applied
Mathematics* **29** (1975), No. 3, 388-405.

7.
N.
Megiddo, "Partial
and complete cyclic orders," *Bulletin of the American Mathematical
Society* **82** (1976), No. 2, 274-276.

8.
N.
Megiddo, "On
monotonicity in parametric linear complementarity problems," *Mathematical
Programming* **12** (1977), No. 1, 60-66.

9.
N.
Megiddo and M. Kojima, "On the existence and
uniqueness of solutions in nonlinear complementarity theory," *Mathematical
Programming*** 12** (1977), No. 1, 110-130.

10.
N.
Megiddo, "A
monotone linear complementarity problem with feasible solutions but no
complementary solutions," *Mathematical Programming* **12**
(1977), No. 1, 131-132.

11.
N.
Megiddo, "A
good algorithm for lexicographically optimal flows in multi-terminal networks,"
*Bulletin of the American Mathematical Society* **83** (1977), No. 3,
407-409.

12.
N.
Megiddo, "Mixtures
of order matrices and generalized order matrices," *Discrete
Mathematics* **19** (1977), No. 2, 177-181.

13.
Z.
Galil and N. Megiddo, "Cyclic ordering is
NP-complete," *Theoretical Computer Science* **5** (1977), No.
2, 179-182.

14.
N.
Megiddo and A. Tamir, "An *O*(*n log n*) algorithm for a class of matching
problems," *SIAM Journal on Computing* **7** (1978), No. 2,
154-157.

15.
N.
Megiddo, "On
the parametric nonlinear complementarity problem," *Mathematical
Programming Study* **7** (1978), ("Complementarity and fixed point
problems," M. L. Balinski and R. W. Cottle, eds.), 142-150.

16.
N.
Megiddo, "Cost
allocation for Steiner trees," *Networks ***8** (1978), No. 1,
1-6.

17.
N.
Megiddo, "Computational
complexity of the game theory approach to cost allocation on a tree," *Mathematics
of Operations Research* **3** (1978) No. 3, 189-196.

18.
N.
Megiddo, "Edge three-coloring of tournaments," *SIAM Review* **20**
(1978), No. 3, p. 593.

19.
Z.
Galil and N. Megiddo, "A fast selection
algorithm and the problem of optimum distribution of effort," *Journal
of the Association for Computing Machinery ***26** (1979), No. 1, 58-64.

20.
N.
Megiddo and Z. Galil, "On
Fulkerson's conjecture about consistent labeling processes," *Mathematics
of Operations Research ***4** (1979), No. 3, 265-267.

21.
N.
Megiddo, "Combinatorial
optimization with rational objective functions," *Mathematics of
Operations Research ***4** (1979) 414-424.

22.
M.
I. Kamien and N. Megiddo, "An intergenerational
cake eating game," *Economics Letters* **2** (1979) 5-7.

23.
E.
Kalai and N. Megiddo, "Path-independent
choices," *Econometrica** ***48**
(1980), No. 3, 781-784.

24.
N.
Megiddo, "On
repeated games with incomplete information played by non-Bayesian players,"
*International Journal of Game Theory ***9** (1980), No. 3, 157-167.

25.
N.
Megiddo, A. Tamir, E. Zemel
and R. Chandrasekaran, "An *O*(*n
*(*log n*) *^2*) algorithm for the *k'th*
nearest pair in a tree with applications to location problems," *SIAM
Journal on Computing ***10** (1981), No. 2, 328-337.

26.
N.
Megiddo, "On
the complexity of the one-terminal network design problem," *Operations
Research Letters* **1** (1982), No. 3, 105-107.

27.
N.
Megiddo, "Is
binary encoding appropriate for the problem-language relationship?" *Theoretical
Computer Science* **19** (1982) 337-341.

28.
N.
Megiddo and A. Tamir, "On
the complexity of locating linear facilities in the plane," *Operations
Research Letters* **1** (1982), No. 5, 194-197.

29.
N.
Megiddo, "Towards
a genuinely polynomial algorithm for linear programming," *SIAM
Journal on Computing* **12** (1983), No. 2, 347-353.

30.
N.
Megiddo, E. Zemel and S. L. Hakimi,
"The
maximum coverage location problem," *SIAM Journal on Algebraic and
Discrete Methods ***4** (1983), No. 2, 253-261.

31.
N.
Megiddo and A. Tamir, "Finding
least-distances lines," *SIAM Journal on Algebraic and Discrete
Methods ***4** (1983), No. 2, 207-211.

32.
N.
Megiddo, "Linear-time
algorithms for linear programming in *R^3* and related problems,"
*SIAM Journal on Computing* **12** (1983), No. 4, 759-776.

33.
N.
Megiddo and A. Tamir, "New results on the
complexity of *p*-center problems," *SIAM Journal on Computing*
**12** (1983), No. 4, 751-758.

34.
N.
Megiddo, "Applying
parallel computation algorithms in the design of serial algorithms," *Journal
of the Association for Computing Machinery ***30** (1983), No. 4,
852-865.

35.
N.
Megiddo, "The
weighted Euclidean 1-center problem," *Mathematics of Operations
Research ***8** (1983), No. 4, 498-504.

36.
N.
Megiddo, "Linear
programming in linear time when the dimension is fixed," *Journal of
the Association for Computing Machinery ***31** (1984), No. 1, 114-127.

37.
N.
Megiddo and K. J. Supowit, "On
the complexity of some common geometric location problems," *SIAM
Journal on Computing*** 13** (1984), No. 1, 182-196.

38.
I.
Adler, N. Megiddo and M. J. Todd, "New results on the
behavior of simplex algorithms," *Bulletin of the American
Mathematical Society ***11** (1984), No. 2, 378-382.

39.
N.
Megiddo and T. Ichimori, "A two-resource
allocation problem solvable in linear time," *Mathematics of
Operations Research*** 10** (1985), No. 1, 7-16.

40.
R.
Hassin and N. Megiddo, "An optimal
algorithm for finding all the steps of a monotone step-function," *Journal
of Algorithms*** 6** (1985) 265-274.

41.
I.
Adler and N. Megiddo, "A simplex algorithm
whose average number of steps is bounded between two quadratic functions of the
smaller dimension," *Journal of the Association for Computing
Machinery ***32** (1985) 871-895.

42.
N.
Megiddo, "Partitioning
with two lines in the plane," *Journal of Algorithms ***6**
(1985) 430-433.

43.
N.
Megiddo, "A
note on the generality of the self-dual algorithm with various starting points,"
*Methods of Operations Research*** 49** (1985) 271-275.

44.
J.
Y. Halpern, N. Megiddo and A. A. Munshi, "Optimal precision in
the presence of uncertainty," *Journal of Complexity ***1**
(1985), No. 2, 170-196.

45.
N.
Megiddo and E. Zemel, "A randomizing *O*(*n log n*) algorithm for the weighted
Euclidean 1-center problem," *Journal of Algorithms ***7**
(1986) 358-368..

46.
N.
Megiddo, "On
the expected number of linear complementarity cones intersected by random and
semi-random rays," *Mathematical Programming*** 35** (1986),
No. 2, 225-235.

47.
N.
Megiddo, "Improved
asymptotic analysis of the average number of steps performed by the self-dual
simplex algorithm," *Mathematical Programming ***35** (1986)
140-172.

48.
N.
Megiddo, "Dynamic
location problems," *Annals of Operations Research ***6**
(1986) 313-319.

49.
J.
O'Rourke, S. R. Kosaraju and N. Megiddo,
"Computing circular separability," *Discrete
and Computational Geometry* **1** (1986) 105-113.

50.
N.
Megiddo, "A
note on degeneracy in linear programming," *Mathematical Programming*
**35** (1986), No. 3, 365-367.

51.
N.
Megiddo, "Introduction: New approaches to linear programming," *Algorithmica
***1** (1986) 387-394.

52.
N.
Megiddo, "Linear
programming (1986)," *Annual Review of Computer Science ***2**
(1987) 119-145.

53.
N.
Megiddo, "On
the complexity of polyhedral separability,"*
Discrete and Computational Geometry* **3** (1988) 325-327.

54.
N.
Megiddo and U. Vishkin, "On finding a minimum
dominating set in a tournament," *Theoretical Computer Science* **61**
(1988) 307-316.

55.
N.
Megiddo, S. L. Hakimi, M. R. Garey,
D. S. Johnson and C. H. Papadimitriou, "On the
complexity of searching a graph," *Journal of the Association for
Computing Machinery ***35** (1988) 18-44.

56.
R.
Hassin and N. Megiddo, "On orientations and
shortest paths," *Linear Algebra and Its Applications ***114/115**
(1989) 589-602.

57.
N.
Megiddo, "On
computable beliefs of rational machines,"* Games and Economic
Behavior ***1** (1989) 144-169.

58.
N.
Megiddo and B. O'Neill, " 'Inscrutable'
badges for verifying a mobile missile quota," *Defense Analysis* **5**
(1989) 260-262.

59.
N.
Megiddo and R. Chandrasekaran, "On the
epsilon-perturbation method for avoiding degeneracy,"* Operations
Research Letters* **8** (1989) 305-308.

60.
N.
Megiddo, "Extending
NC and RNC algorithms,"* Algorithmica* **4 **(1989) 511-517.

61.
N.
Megiddo and M. Shub, "Boundary behavior of
interior point algorithms in linear programming,"* Mathematics of
Operations Research ***14** (1989), No. 1, 97-146.

62.
N.
Megiddo, "On
the ball spanned by balls,"* Discrete and Computational Geometry ***4**
(1989) 605-610.

63.
R.
Fagin, J. Y. Halpern and N. Megiddo, "A logic for
reasoning about probabilities," *Information and Computation***
87** (1990) 78-128.

64.
N.
Megiddo, "On
solving the linear programming problem approximately," *Contemporarty** Mathematics* **114** (1990)
35-50.

65.
G.
S. Lueker, N. Megiddo and V. Ramachandran, "Linear
programming with two variables per inequality in poly log time," *SIAM
Journal on Computing* **19** (1990) 1000-1010.

66.
N.
Megiddo, "On
the complexity of some geometric problems in unbounded dimension,"*
Journal of Symbolic Computation* **10** (1990) 327-334.

67.
R.
Hassin and N. Megiddo, "Approximation
algorithms for hitting objects by straight lines,"* Discrete Applied
Mathematics* **30** (1991) 29-42.

68.
M.
Kojima and N. Megiddo, "The relation
between the path of centers and Smale's
regularization of the linear programming problem,"* Linear Algebra
and Its Applications ***152** (1991) 135-139.

69.
N.
Megiddo and C.H. Papadimitriou, "A note on total
functions, existence theorems and complexity,"* Theoretical Computer
Science* **81** (1991) 317-324.

70.
M.
Kojima, N. Megiddo and T. Noma, "Homotopy
continuation methods for nonlinear complementarity problems,"*
Mathematics of Operations Research* **16** (1991) 754-774.

71.
R.
Hassin and N. Megiddo, "Exact computation of
optimal inventory policies over an unbounded horizon,"* Mathematics
of Operations Research* **16** (1991) 534-546.

72.
M.
Kojima, N. Megiddo, T. Noma and A. Yoshise, "A unified approach
to interior point algorithms for linear complementarity problems: A summary,"
*Operations Research Letters ***10** (1991) 247-254.

73.
N.
Megiddo, "On
finding primal- and dual-optimal bases,"* ORSA Journal of Computing ***3**
(1991) 63-65.

74.
D.
Koller and N. Megiddo, "The complexity of
two-person zero-sum games in extensive form,"* Games and Economic
Behavior* **4** (1992) 528-552.

75.
N.
Megiddo, "A
note on approximate linear programming,"* Information Processing
Letters* **2** (1992) 53.

76.
M.
Kojima, N. Megiddo and Y. Ye, "An interior point
potential reduction algorithm for the linear complementarity problem," *Mathematical
Programming* **54** (1992), No. 3, 267-279.

77.
M.
Kojima, N. Megiddo and S. Mizuno, "A general framework
of continuation methods for complementarity problems,"* Mathematics
of Operations Research* **18** (1993) 945-963.

78.
M.
Kojima, N. Megiddo and S. Mizuno, "Theoretical convergence
of large-step primal-dual interior point algorithms for linear programming," *Mathematical
Programming ***59** (1993) 1-22.

79.
E.
Cohen and N. Megiddo, "Strongly polynomial-time and NC algorithms for
detecting cycles in dynamic graphs," *Journal of the Association for
Computing Machinery ***40** (1993) 791-832.

80.
N.
Megiddo and A. Tamir, "Linear time
algorithms for some separable quadratic programming problems,"*
Operations Research Letters* **13** (1993) 203-211.

81.
D.
S. Hochbaum, N. Megiddo, J. Naor, and A. Tamir, "Tight bounds
and 2-approximation algorithms for integer programs with two variables per
inequality,"* Mathematical Programming* **62** (1993) 69-84.

82.
M.
Kojima, N. Megiddo and S. Mizuno, "A primal-dual infeasible-interior-point
algorithm for linear programming," *Mathematical Programming ***61**
(1993) 263-280.

83.
D.
Koller and N. Megiddo, "Constructing
small sample spaces satisfying given constants,"* SIAM Journal on
Discrete Mathematics* **7** (1994) 260-274.

84.
N.
Alon and N. Megiddo, "Parallel linear
programming in fixed dimension almost surely in constant time,"*
Journal of the Association for Computing Machinery ***41** (1994), No. 2,
422-434.

85.
E.
Cohen and N. Megiddo, "Improved algorithms for
linear inequalities with two variables per inequality,"* SIAM
Journal on Computing* **23** (1994) 1313-1350.

86.
E.
Cohen and N. Megiddo, "Algorithms and
complexity analysis of some flow problems,"* Algorithmica ***11**
(1994) 320-340.

87.
E.
Cohen and N. Megiddo, "New algorithms for
generalized network flows,"* Mathematical Programming ***64**
(1994) 325-336.

88.
D.
Koller, N. Megiddo and B. von Stengel, "Efficient
computation of equilibria for extensive two-person games,"* Games
and Economic Behavior* **14** (1996) 220-246.

89.
D.
Koller and N. Megiddo, "Finding mixed
strategies with small supports in extensive form games,"*
International Journal of Game Theory ***25** (1996) 73-92.

90.
T.
Hegedus and N. Megiddo, "On the geometric separability of boolean functions,"*
Discrete Applied Mathematics* **66** (1996) 205-218.

91.
M.
Ajtai and N. Megiddo, "A deterministic poly(*log log n*)-time *n*-processor
algorithm for linear programming in fixed dimension,"* SIAM Journal
on Computing ***25** (1996) 1171-1195.

92.
N.
Megiddo, S. Mizuno and T. Tsuchiya, "A linear
programming instance with many crossover events," *Journal of
Complexity*** 12** (1996) 474-479.

93.
M.
Kojima, N. Megiddo and S. Mizuno, "A conjugate
direction method for approximating the analytic center of a polytope,"*
Journal of Inequalities and Applications ***2** (1998) 181-194.

94.
N.
Megiddo, S. Mizuno, and T. Tsuchiya, "A modified
layered-step interior-point algorithm for Linear Programming," *Mathematical
Programming ***82** (1998), No. 3, 339-355.

95.
P.
Beling and N. Megiddo, "Using fast matrix
multiplication to find basic solutions,"* Theoretical Computer
Science ***205 **(1998) 307-316.

96.
T.
Feder, N. Megiddo, and S. A. Plotkin,
"A sublinear parallel algorithm for stable matching,"
*Theoretical Computer Science ***233** (2000) 297-308.

97.
M.
Ajtai, N. Megiddo and O. Waarts,
"Improved
algorithms and analysis for secretary problems and generalizations," *SIAM
Journal on Discrete Mathematics ***14** (2001), No. 1, 1-27.

98.
N.
Megiddo and D. S. Modha, "One up on LRU," *;**login:* **28** (2003), No. 4, 7-11.

99.
N.
Megiddo and D. S. Modha, "Outperforming
LRU with an adaptive replacement cache algorithm," *Computer* **37**
(2004), No. 4, 58-65.

100. D. P. de Farias and N. Megiddo,
"Combining expert advice in reactive environments," *J. ACM* **53**
(2006), No. 5, 762-799.

101. V. Markl,
P. Haas, M. Kutsch, N. Megiddo, U. Srivastava, and T.M. Tran, "Consistently
selectivity estimation via maximum entropy," *VLDB
Journal* **16** (2007), No. 1, 55-76.

102. S. Agrawal, N. Megiddo and B. Armbruster, "Equilibrium in Prediction Markets with
Buyers and Sellers," *Economics
Letters ***109** (2010), No.
1, 46 - 49.

1. Z. Galil and N. Megiddo, "A fast selection algorithm and the problem of optimum distribution of effort," Proceedings of Conference on Theoretical Computer Science, University of Waterloo, Waterloo, Ontario, Canada, 1977.

2. N. Megiddo, "Combinatorial optimization with rational objective functions," Proceedings of the 10th Annual ACM Symposium on Theory of Computing (1978), ACM, New York, 1978, pp. 1-12.

3. N. Megiddo, S. L. Hakimi, M. R. Garey, D. S. Johnson and C. H. Papadimitriou, "The complexity of searching a graph," Proceedings of the 22nd IEEE Symposium on Foundations of Computer Science (1981), IEEE Computer Society Press, Los Angeles, 1981, pp. 376-385.

4. N. Megiddo, "Applying parallel computation algorithms in the design of serial algorithms," Proceedings of the 22nd IEEE Symposium on Foundations of Computer Science (1981), IEEE Computer Society Press, Los Angeles, 1981, pp. 399-408

5.
N.
Megiddo, "Linear-time algorithms for linear programming in *R^3* and
related problems," Proceedings of the 23rd IEEE Symposium on Foundations
of Computer Science (1982), IEEE Computer Society Press, Los Angeles, 1982, pp.
329-338.

6. I. Adler and N. Megiddo, "A simplex algorithm whose average number of steps is bounded between two quadratic functions of the smaller dimension," Proceedings of the 16th ACM Symposium on the Theory of Computing (1984), ACM, New York, 1984, pp. 312-323.

7. J. Y. Halpern, N. Megiddo and A. A. Munshi, "Optimal precision in the presence of uncertainty," Proceedings of the Seventeenth Annual ACM Symposium on Theory of Computing (1985), ACM, New York, 1985, pp. 346-355.

8.
N.
Megiddo and A. Wigderson, "On play by means of
computing machines," in: *Theoretical Aspects of Reasoning about
Knowledge*, J. Y. Halpern, ed., Morgan Kaufmann Publishers, Inc., Los Altos,
California, 1986, pp. 259-274.

9.
N.
Megiddo, "Linear programming (1986)," *Annual Review of Computer
Science ***2** (1987) pp. 119-145.

10.
N.
Megiddo, "On the
complexity of linear programming," in: *Advances in economic theory:
Fifth world congress*, T. Bewley, ed., Cambridge
University Press, Cambridge, 1987, pp. 225-268.

11.
N.
Megiddo, "Pathways
to the optimal set in linear programming," in: *Progress in
Mathematical Programming: Interior-Point and Related Methods*, N. Megiddo,
ed., Springer-Verlag, New York, 1988, pp. 131-158;
also in: Proceedings of the 7th Mathematical Programming Symposium of Japan,
Nagoya, Japan, 1986, pp. 1-35.

12. R. Fagin, J. Y. Halpern and N. Megiddo, "A logic for reasoning about probabilities," Proceedings of the Third IEEE Symposium on Logic in Computer Science, 1988, pp. 277-291.

13. G. S. Lueker, N. Megiddo and V. Ramachandran, "L inear programming with two variables per inequality in poly log time," Proceedings of the 18th Annual ACM Symposium on Theory of Computing (1986), ACM, New York, 1986, pp. 196-205.

14.
E.
Cohen and N. Megiddo, "Recognizing
properties of periodic graphs," in: *Applied Geometry and Discrete
Mathematics - The Victor Klee Festschrift,* P. Gritzmann
and B. Sturmfels, Eds., DIMACS Series in Discrete
Mathematics and Theoretical Computer Science Vol. 4, American Mathematical
Society and ACM, Providence, RI, 1991, pp. 135-146.

15.
N.
Megiddo, "Linear
Programming,"* Encyclopedia of Microcomputers* Vol. **10**,
Marcel Dekker, Inc., New York, 1992, pp. 205-210.

16. E. Cohen and N. Megiddo, "Strongly polynomial-time and NC algorithms for detecting cycles in dynamic graphs," Proceedings of the 21st Annual ACM Symposium on Theory of Computing (1989), ACM, New York, 1989, pp. 523-534.

17.
N.
Megiddo, "A
general NP-completeness theorem," in: *From topology to computation
- from Proceedings of the Smale Fest*, M. Hersh, J. Marsden, and M. Shub,
Eds., Springer-Verlag, New York, 1993, pp. 432-442.

18.
E.
Cohen and N. Megiddo, "Maximizing
concave functions in fixed dimension," in: *Complexity in Numerical
Optimization*, P. M. Pardalos, Ed., World
Scientific, Singapore, 1993, pp. 74-87.

19. N. Megiddo, M. Naor, and D. P. Anderson, "The minimum reservation rate problem in digital audio/video systems," in: Proceedings of ISTCS'93 - The Second Israel Symposium on the Theory of Computing and Systems, IEEE Computer Society Press, San Diego, 1993, pp. 43-48.

20. D. Koller and N. Megiddo, "Constructing small sample spaces satisfying given constraints," Proceedings of the 25th Annual ACM Symposium on Theory of Computing (1993), ACM, New York, 1993, pp. 268-277.

21. T. Feder, N. Megiddo, and S. A. Plotkin, "A sublinear parallel algorithm for stable matching," Proceedings of the Fifth Annual ACM/SIAM Symposium on Discrete Algorithms (1994), pp. 632-637.

22. N. Alon and N. Megiddo, "Parallel linear programming in fixed dimension almost surely in constant time," Proceedings of the 31st IEEE Symposium on Foundations of Computer Science (1990), IEEE Computer Society Press, Los Angeles, 1990, pp. 574-582.

23.
N.
Megiddo, "On
probabilistic machines, bounded rationality, and average-case complexity,"
in: *Essays in Game Theory in Honor of Michael Maschler*,
Springer-Verlag, New York, 1994, pp. 123-128.

24. E. Cohen and N. Megiddo, "Improved algorithms for linear inequalities with two variables per inequality," Proceedings of the 23rd Annual ACM Symposium on Theory of Computing (1991), ACM, New York, 1991, pp. 145-154.

25. E. Cohen and N. Megiddo, "Algorithms and and complexity analysis of some flow problems," Proceedings of the Second Annual ACM/SIAM Symposium on Discrete Algorithms (1991), pp. 120-130.

26. M. Kojima, N. Megiddo, S. Mizuno and S. Shindoh, "Decomposition in Interior-Point Methods," in: Proceedings Optimization - Modeling and Algorithms, The Institute of Statistical Mathematics, Minato-ku, Tokyo, March 1994..

27. E. Cohen and N. Megiddo, "New algorithms for generalized network flows," Proceedings of ISTCS'92 - The 1992 Israel Symposium on the Theory of Computing and Systems, Lecture Notes in Computer Science, Vol. 601, D. Dolev, Z. Galil, and M. Rodeh, Eds., Springer-Verlag, Berlin, 1992, pp. 103-114.

28. D. Koller, N. Megiddo and B. von Stengel, "Fast algorithms for finding randomized strategies in game trees," Proceedings of 26th Annual ACM Symposium on Theory of Computing (1994), ACM, New York, 1994, pp. 750-759.

29.
M.
Ajtai and N. Megiddo, "A deterministic poly(*log log n*)-time *n*-processor
algorithm for linear programming in fixed dimension," Proceedings of
the 24th Annual ACM Symposium on Theory of Computing (1992), ACM, New York,
1992, pp. 327-337.

30. M. Ajtai, N. Megiddo and O. Waarts, "Improved algorithms and analysis for secretary problems and generalizations," Proceedings of the 36th IEEE Symposium on Foundations of Computer Science (1995) , IEEE Computer Society Press, Los Angeles, 1995, pp. 473-482.

31. Q. Huang, B. Dom, N. Megiddo and W. Niblack, "Segmenting and representing background in color images," in: Proceedings of the 13th International Conference on Pattern Recognition (ICPR'96, Technical University of Vienna, Austria, August 25-30, 1996), International Association for Pattern Recognition (IAPR), 1996.

32. Q. Huang and N. Megiddo, "Color image background segmentation and representation," in: Proceedings of the 1996 IEEE International Conference on Image Processing (ICIP'96, September 16-19, 1996, Lausanne, Switzerland), IEEE Signal Processing Society, 1996.

33. M. Dyer and N. Megiddo, "Linear programming in low dimensions," in: CRC Handbook of Discrete and Computational Geometry, E. Goodman and J. O'Rourke, Eds., CRC Press, Inc., Boca Raton, New York, 1997, pp. 699-710.

34. C.-T. Ho, R. Agrawal, N. Megiddo and R. Srikant, "Range queries in OLAP data cubes," Proceedings of the 1997 ACM-SIGMOD International Conference on Management of Data, Tucson, Arizona, May 1997, pp. 73-88.

35. N. Megiddo and V. Sarkar "Optimal weighted loop fusion for parallel programs," Proceedings of the Ninth Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA'97), Newport, Rhode Island, June 22-25, 1997, pp. 282-291

36. S. Sarawagi, R. Agrawal, and N. Megiddo, "Discovery-driven exploration of OLAP data cubes," Advances in Database Technology - EDBT'98, 6th International Conference on Extending Database Technology, Valencia, Spain, March 23-27, 1998, Proceedings. Lecture Notes in Computer Science 1377 Springer 1998, pp. 168-182.

37. N. Megiddo and R. Srikant, "Discovering predictive association rules," Proceedings of the Fourth International Conference on Knowledge Discovery and Data Mining (KDD-98), August 27-31, 1998, New York, pp. 274-278.

38. J. Shepherd, X. Zhu and N. Megiddo, "A fast indexing method for multidimensional nearest neighbor search," Proc. of the IS&T/SPIE Conf. on Storage and Retrieval of image and video databases VII, pp. 350-355, 1999.

39. T. Syeda-Mahmood, P. Raghavan and N. Megiddo, "Interval hash tree: An efficient index structure for searching object queries in large image databases," IEEE Workshop on Content-Based Access of Image and Video Libraries (CBAIVL-2000; in conjunction with IEEE CVPR-2000), Hilton Head, South Carolina, June 12, 2000.

40. V. Sarkar and N. Megiddo, "An analytical model for loop tiling and its solution," ISPASS-2000, IEEE International Symposium on Performance Analysis of Systems and Software, April 24-25, 2000, Austin, Texas.

41. J. Langford, M. Seeger and N. Megiddo, "An Improved Predictive Accuracy Bound for Averaging Classifiers," Proc. of the 18th International Conference on Machine Learning (ICML-2001) June 28 - July 1, 2001, Williams College, Morgan-Kaufmann Publishers, San Francisco, 2001, pp. 290-297.

42. F. Naumann, C. T. Ho, X. Tian, L. Haas and N. Megiddo, "Attribute Classification Using Feature Analysis," 18th IEEE International Conference on Data Engineering (ICDE), San Jose, California, February 26 - March 1, 2002.

43. J. Rao, C. Zhang, N. Megiddo and G. M. Lohman, "Automating Physical Database Design in a Parallel Database," ACM SIGMOD Conference, Madison, Wisconsin, June 3-6, 2002, pp. 558-569.

44. N. Megiddo and D. S. Modha, "ARC: A Self-Tuning, Low Overhead Replacement Cache," Proc. of the 2nd USENIX Conference on File and Storage Technologies (FAST-2003) March 31 - April 2, 2003, San Francisco, pp. 115-130.

45.
D.
de Farias and N. Megiddo, "How to
Combine Expert (or Novice) Advice when Actions
Impact the Environment," Proceedings
of Neural Information Processing Systems (NIPS 2003).

46.
M.
Dyer, N. Megiddo and E. Welzl, "Linear
Programming," in: CRC Handbook of Discrete and Computational Geometry,
Second Edition, E. Goodman and J. O'Rourke, Eds., CRC Press, Inc., Boca Raton,
New York, 2004, pp. 999-1014.

47.
D.
de Farias and N. Megiddo, "Exploration-Exploitation Tradeoffs for Experts
Algorithms in Reactive Environments," Proceedings of Neural Information
Processing Systems (NIPS 2004).

48.
V.
Markl, N. Megiddo, M. Kutsch,
T. M. Tran, P. Hass, and U. Srinivasta,
"Consistently Estimating the Selectivity of Conjuncts of Predicates,"
Proceedings of VLDB 2005, pp. 373-384.

49.
U.
Srivastava, P. Hass, V. Markl, N. Megiddo, M. Kutsch, and T. M. Tran, "ISOMER: Consistent Histogram
Construction Using Query Feedback," 22nd IEEE International
Conference on Data Engineering (ICDE), 2006.

50.
M.
Kutsch, V. Markl, P. Hass,
N. Megiddo, and T. M. Tran, "Integrating a Maximum-Entropy Cardinality
Estimator Into DB2 UDB," Advances in Database Technology -- EDBT 2006 10 International
Conference on Extending Database Technology, Munich, Germany, 26-31 March 2006,
pp. 1092-1096.

51.
V.
Markl, M. Kutsch, T. M.Tran, P. J. Haas, and N. Megiddo, "MAXENT: consistent cardinality estimation in action," Proceedings
of the ACM SIGMOD International Conference on Management of Data, Chicago,
Illinois, USA, June 27-29, 2006. ACM 2006, pp. 775-777.

52.
E.
Hazan and N. Megiddo, "Online Learning
with Prior Knowledge," in: Learning Theory, 20^{th} Annual
Conference on Learning Theory, COLT 2007, San Diego, CA, June 2007, LNAI 4539,
Springer, pp. 499-513.

53.
N. Megiddo and V. Vazirani, "Continuity Properties of Equilibrium Prices and
Allocations in Linear Fisher Markets," Proceedings
of Internet and Network Economics, Third International Workshop, WINE 2007,
San Diego, CA, USA, December 12-14, 2007, Lecture Notes in Computer Science 4858 Springer,
2007, pp. 362-367.

54.
D.
Dash, J. Rao, N. Megiddo, A. Ailamaki, and G. M. Lohman, Dynamic faceted search for discovery-driven
analysis," Proceedings of the 17th ACM Conference on Information and
Knowledge Management, CIKM 2008, Napa Valley, California, USA, October 2008.
ACM 2008, pp. 3-12.

55.
H. Jin, J. Lotspiech and N.
Megiddo, "Efficient Coalition
Detection in Traitor Tracing," Proceedings
of The IFIP Tc 11 23^{rd} International
Information Security Conference, 2008,
pp.365-380.

56. H. Jin, J. Lotspiech, M. Nelson and N. Megiddo, "Adaptive Traitor
Tracing for Large Anonymous Attack," Proceedings
of the 8th ACM workshop on Digital rights management, Alexandria, VA, USA,
October 27, 2008, ACM 2008, pp. 1-8.

57.
J. Mahmud, M. X. Zhou, N. Megiddo, J. Nichols and C. Drews,
"Recommending targeted
strangers from whom to solicit information on social media," Proceedings of International Conference on Intelligent Computer
Interfaces (IUI 2013),
Santa Monica, Calif., March 19-22, 2013, pp. 37-48.

58.
M.
Hardt, N. Megiddo, C. H. Papadimitriou and M. Wootters, "Strategic Classification,"
in Proceedings of the 2016 ACM Conference on Innovations in Theoretical
Computer Science, Pages 111-122.

1.
N.
Megiddo, "On the nucleolus of a composition of characteristic function
games," Technical Report, Department of Mathematical Sciences, Tel Aviv
University, 1973.

2.
N.
Megiddo, "A generalization of Eaves' odd theorem," Technical Report,
Department of Statistics, Tel Aviv University, 1976.

3.
N.
Megiddo and S. L. Hakimi, "Pursuing mobile
hiders in a graph," Discussion Paper No. 360, Center for Mathematical
Studies in Economics and Management Science, Northwestern University, 1978.

4.
N.
Megiddo, "Applications of modern cryptography to secret voting,"
Technical Report, Department of Statistics, Tel Aviv University, 1980.

5.
N.
Megiddo, "An application of parallel computation to sequential
computation: The problem of cost-effective resource allocation," TWISK
202, National Research Institute for Mathematical Sciences, Council for
Scientific and Industrial Research (CSIR), Pretoria, South Africa, March 1981.

6.
N.
Megiddo, "Parallel
algorithms for finding the maximum and the median almost surely in
constant-time," Technical Report, Graduate School of Industrial
Administration, Carnegie-Mellon University, October 1982.

7.
N.
Megiddo, "Poly-log
parallel algorithms for LP with an application to exploding flying objects,"
Technical Report, Graduate School of Industrial Administration, Carnegie-Mellon
University, November 1982.

8.
N.
Megiddo, "Recognizing 'digital disks'," manuscript, XEROX Palo Alto
Research Center, 1984.

9.
N.
Megiddo, "A variation on Karmarkar's
algorithm," manuscript, IBM San Jose Research Laboratory, San Jose,
California, 1984.

10.
N.
Megiddo, "A
note on sensitivity analysis in algebraic algorithms," Research Report
RJ 4958, IBM Almaden Research Center, San Jose, California, 1985.

11.
N.
Megiddo and E. Zemel, "A randomizing *O*(*n log n*) algorithm for the weighted
Euclidean 1-center problem," Research Report RJ 5005, IBM Almaden Research
Center, San Jose, California, 1985.

12.
N.
Megiddo, "Improved asymptotic analysis of the average number of steps
performed by the self-dual simplex algorithm," Research Report RJ 4962,
IBM Almaden Research Center, San Jose, California, 1985.

13.
N.
Megiddo, "Dynamic location problems," Research Report RJ 4983, IBM
Almaden Research Center, San Jose, California, 1986.

14.
J.
O'Rourke, S. R. Kosaraju and N. Megiddo, "Computing circular separability," Research Report RJ 4986, IBM
Almaden Research Center, San Jose, California, 1986.

15.
N.
Megiddo, "A note on degeneracy in linear programming," Research
Report RJ 4895, IBM Almaden Research Center, San Jose, California, 1985.

16.
N.
Megiddo and A. Wigderson, "On play by means of
computing machines," Research Report RJ 4984, IBM Almaden Research
Center, San Jose, California, 1986.

17.
N.
Megiddo, "Remarks on
bounded rationality," Research Report RJ 5270, IBM Almaden Research
Center, San Jose, California, 1986.

18.
N.
Megiddo, "Introduction: New approaches to linear programming,"
Research Report RJ 5278, IBM Almaden Research Center, San Jose, California,
1986.

19.
N.
Megiddo, "Linear
programming (1986)," Research Report RJ 5405, IBM Almaden Research
Center, San Jose, California, 1986.

20.
N.
Megiddo, "On the
complexity of linear programming," Research Report RJ 4985, IBM
Almaden Research Center, San Jose, California, 1986.

21.
N.
Megiddo, "Are the vertex cover and the dominating set problems equally
hard?," Research Report RJ 5783, IBM Almaden
Research Center, San Jose, California, 1987.

22.
N.
Megiddo, "Pathways to the optimal set in linear programming," Research Report RJ 5295, IBM Almaden Research Center,
San Jose, California, 1986.

23.
N.
Megiddo, "A
note on Karmarkar's projective transformation," IBM Almaden
Research Center, San Jose, California, , December
1988.

24.
N.
Megiddo, "On
the complexity of polyhedral separability,"
Research Report RJ 5252, IBM Almaden Research Center, San Jose, California,
1986.

25.
N.
Megiddo, "Extending
NC and RNC algorithms," Research Report RJ 5294, IBM Almaden Research
Center, San Jose, California, 1986.

26.
N.
Megiddo and M. Shub, "Boundary
behavior of interior point algorithms in linear programming," Research
Report RJ 5319, IBM Almaden Research Center, San Jose, California, 1986.

27.
R.
Hassin and N. Megiddo, "Approximation
algorithms for hitting objects by straight lines," Research Report RJ
5659, IBM Almaden Research Center, San Jose, California, 1987.

28.
N.
Megiddo, "On
the complexity of some geometric problems in unbounded dimension,"
Research Report RJ 5744, IBM Almaden Research Center, San Jose, California,
1987.

29.
N.
Megiddo and U. Vishkin, "On finding a
minimum dominating set in a tournament," Research Report RJ 5745, IBM
Almaden Research Center, San Jose, California, 1987.

30.
N.
Megiddo, "On
the ball spanned by balls," Research Report RJ 5763, IBM Almaden Research
Center, San Jose, California, 1987.

31.
N.
Megiddo, "On
the complexity of solving the generalized set packing problem
approximately," Research Report RJ 5898, IBM Almaden Research Center,
San Jose, California, 1987.

32.
R.
Hassin and N. Megiddo, "On orientations and
shortest paths," Research Report RJ 6008, IBM Almaden Research Center, San
Jose, California, 1987.

33.
N.
Megiddo, "On
computable beliefs of rational machines," Research
Report RJ 6108, IBM Almaden Research Center, San Jose, California, 1988.

34.
R.
Fagin, J. Y. Halpern and N. Megiddo, "A logic for reasoning about
probabilities," Research Report RJ 6190, IBM Almaden Research Center, San
Jose, California, 1988.

35.
N.
Megiddo,
"Switching from a primal-dual Newton algorithm to a primal-dual (interior)
simplex algorithm," Research Report RJ 6327, IBM Almaden Research
Center, San Jose, California, 1988.

36.
N.
Megiddo, "On
finding primal- and dual-optimal bases," Research Report RJ 6328, IBM
Almaden Research Center, San Jose, California, 1988.

37.
N.
Megiddo, "On
finding additive, superadditive and subadditive set-functions subject to linear inequalities,"
Research Report RJ 6329, IBM Almaden Research Center, San Jose, California,
1988.

38.
N.
Megiddo and R. Chandrasekaran, "On the
epsilon-perturbation method for avoiding degeneracy," Research Report
RJ 6330, IBM Almaden Research Center, San Jose, California, 1988.

39.
N.
Megiddo, "A
Note on the Complexity of P-Matrix LCP and Computing an Equilibrium," Research Report
RJ 6439, IBM Almaden Research Center, San Jose, California, 1988.

40.
N.
Megiddo, "On
solving the linear programming problem approximately," Research Report
RJ 6485, IBM Almaden Research Center, San Jose, California, 1988.

41.
M.
Kojima, N. Megiddo and Y. Ye, "An interior
point potential reduction algorithm for the linear complementarity
problem," Research Report RJ 6486, IBM Almaden Research Center, San
Jose, California, 1988.

42.
G.
S. Lueker, N. Megiddo and V. Ramachandran, "Linear
programming with two variables per inequality in poly log time,"
Research Report RJ 6491, IBM Almaden Research Center, San Jose, California,
1988.

43.
R.
Hassin and N. Megiddo, "Exact computation
of optimal inventory policies over an unbounded horizon,"
Research Report RJ 6492, IBM Almaden Research Center, San Jose, California,
1988.

44.
M.
Kojima, N. Megiddo and T. Noma, "Homotopy
continuation methods for nonlinear complementarity problems,"
Research Report RJ 6638, IBM Almaden Research Center, San Jose, California,
1988.

45.
N.
Megiddo, "On
probabilistic machines, bounded rationality, and average-case complexity,"
Research Report RJ 7039, IBM Almaden Research Center, San Jose, California,
1989.

46.
M.
Kojima and N. Megiddo, "The relation between
the path of centers and Smale's regularization of the
linear programming problem," Research Report RJ 7069, IBM Almaden
Research Center, San Jose, California, 1989.

47.
N.
Megiddo and C.H. Papadimitriou, "A note on total
functions, existence theorems and complexity," Research Report RJ
7091, IBM Almaden Research Center, San Jose, California, 1989.

48.
N.
Alon and N. Megiddo, "Parallel linear
programming in fixed dimension almost surely in constant time,"
Research Report RJ 7245, IBM Almaden Research Center, San Jose, California,
1990.

49.
E.
Cohen and N. Megiddo, "Recognizing properties of periodic graphs,"
Research Report RJ 7246, IBM Almaden Research Center, San Jose, California,
1990.

50.
M.
Kojima, N. Megiddo, T. Noma and A. Yoshise, "A unified approach to interior point
algorithms for linear complementarity problems," Research Report RJ 7493,
IBM Almaden Research Center, San Jose, California, 1990.

51.
E.
Cohen and N. Megiddo, "Strongly polynomial-time and NC algorithms for
detecting cycles in dynamic graphs," Research Report RJ 7587, IBM Almaden
Research Center, San Jose, California, 1990.

52.
E.
Cohen and N. Megiddo, "Algorithms and and complexity analysis of some flow problems,"
Research Report RJ 7626, IBM Almaden Research Center, San Jose, California,
1990.

53.
E.
Cohen and N. Megiddo, "Maximizing
concave functions in fixed dimension," Research Report RJ 7656, IBM
Almaden Research Center, San Jose, California, 1990.

54.
N.
Megiddo, "A general NP-completeness theorem," Research Report RJ
7677, IBM Almaden Research Center, San Jose, California, 1990.

55.
M.
Kojima, N. Megiddo and S. Mizuno, "A general framework
of continuation methods for complementarity problems," Research Report
RJ 7720, IBM Almaden Research Center, San Jose, California, 1990.

56.
D.
Koller and N. Megiddo, "The complexity of
two-person zero-sum games in extensive form," Research Report RJ 7837,
IBM Almaden Research Center, San Jose, California, 1990.

57.
M.
Kojima, N. Megiddo and S. Mizuno, "Theoretical
convergence of large-step primal-dual interior point algorithms for linear
programming," Research Report RJ 7872, IBM Almaden Research Center,
San Jose, California, 1990.

58.
E.
Cohen and N. Megiddo, "Improved algorithms
for linear inequalities with two variables per inequality," Research Report
RJ 8187, IBM Almaden Research Center, San Jose, California, 1991.

59.
E.
Cohen and N. Megiddo, "New algorithms for
generalized network flows," Research Report RJ 8188, IBM Almaden Research
Center, San Jose, California, 1991.

60.
D.
Koller and N. Megiddo, "Finding mixed
strategies with small supports in extensive form games," Research
Report RJ 8380, IBM Almaden Research Center, San Jose, California, 1991.

61.
M.
Kojima, N. Megiddo and S. Mizuno, "A primal-dual
exterior point algorithm for linear programming," Research
Report RJ 8500, IBM Almaden Research Center, San Jose, California, 1991.

62.
N.
Megiddo and A. Tamir, "Linear time
algorithms for some separable quadratic programming problems,"
Research Report RJ 8501, IBM Almaden Research Center, San Jose, California,
1991.

63.
M.
Kojima, N. Megiddo and S. Mizuno, "A conjugate direction
method for approximating the analytic center of a polytope,"
Research Report RJ 8540, IBM Almaden Research Center, San Jose, California,
1991.

64.
D.
Koller and N. Megiddo, "Constructing small
sample spaces satisfying given constraints," Research Report RJ 8597,
IBM Almaden Research Center, San Jose, California, 1992.

65.
N.
Megiddo, "A
note on approximate linear programming," Research Report RJ 8634, IBM
Almaden Research Center, San Jose, California, 1992.

66.
N.
Megiddo, "The least index pivot rule with randomly permuted columns,"
Research Report RJ 9072, IBM Almaden Research Center, San Jose, California,
1992.

67.
M.
Kojima, N. Megiddo, and S. Mizuno, "A Lagrangian
relaxation method for approximating the analytic center of a polytope," Research Report
RJ 9075, IBM Almaden Research Center, San Jose, California, 1992.

68.
T.
Hegedus and N. Megiddo, "On the Geometric Separability of Boolean Functions," Research
Report RJ 9147, IBM Almaden Research Center, San Jose, California, 1992.

69.
M.
Ajtai and N. Megiddo, "A deterministic poly(*log log n*)-time
*n*-processor algorithm for linear programming in fixed dimension,"
Research Report RJ 9204, IBM Almaden Research Center, San Jose, California,
1993.

70.
P.
Beling and N. Megiddo, "Using fast matrix
multiplication to find basic solutions," Research Report RJ 9234, IBM Almaden
Research Center, San Jose, California, 1993.

71.
T.
Feder, N. Megiddo, and S. A. Plotkin,
"A sublinear parallel algorithm for stable matching,"
Research Report RJ 9327, IBM Almaden Research Center, San Jose, California,
1993.

72.
M.
Kojima, N. Megiddo, S. Mizuno and S. Shindoh, "Horizontal and
Vertical Decomposition in Interior-Point Methods for Linear Programming"
Research Report RJ 9901, IBM Almaden Research Center, San Jose, California,
1994.

73.
D.
Koller, N. Megiddo and B. von Stengel, "Efficient computation
of equilibria for extensive two-person games," Research Report RJ
9907, IBM Almaden Research Center, San Jose, California, 1994.

74.
N.
Megiddo, M. Naor, and D. P. Anderson, "The minimum
reservation rate problem in digital audio/video systems," Research
Report RJ 9917, IBM Almaden Research Center, San Jose, California, 1994.

75.
M.
Ajtai, N. Megiddo and O. Waarts,
"Improved
algorithms and analysis for secretary problems and generalizations,"
Research Report RJ 9968, IBM Almaden Research Center, San Jose, California,
1995.

76.
N.
Megiddo, S. Mizuno and T. Tsuchiya, "A linear programming instance with
many crossover events," Research Report RJ 9978, IBM Almaden Research
Center, San Jose, California, 1995.

77.
N.
Megiddo, "Finding a line
of sight through boxes in d-space in linear time," Research Report RJ
10018, IBM Almaden Research Center, San Jose, California, 1996.

78.
S.
Mizuno, T. Tsuchiya and N. Megiddo, "A modified layered-step
interior-point algorithm for linear programming," Research Report 10028,
IBM Almaden Research Center, San Jose, California, 1996.

79.
S.
Juge, N. Megiddo and E. Schraner,
"Simulation and Optimization of HDA Testing'', Research Report RJ 10037,
IBM Almaden Research Center, San Jose, CA 1996.

80.
N.
Megiddo, "Toll Savings in the Operation of ISDN Lines,'' Research Report
RJ 10053, IBM Almaden Research Center, San Jose, CA 1996.

81.
N.
Megiddo, "The Variance of the Gini Index
Estimator,'' Research Report RJ 10054, IBM Almaden Research Center, San Jose,
CA 1996.

82.
C.-T.
Ho, R. Agrawal, N. Megiddo and R. Srikant,
"Range queries in OLAP data cubes," Research Report RJ 10070, IBM
Almaden Research Center, San Jose, CA 1997.

83.
C.-T.
Ho, N. Megiddo, and J. J. Tsay, "Fast
algorithms for range-max queries in OLAP data cubes," Research Report
RJ 10071, IBM Almaden Research Center, San Jose, CA 1997.

84.
N.
Megiddo and U. Shaft, "Efficient
nearest neighbor indexing based on a collection of space filling curves,"
Research Report RJ 10093, IBM Almaden Research Center, San Jose, CA, 1997. (See also U.S. Patent `6,148,295)`

85.
N.
Megiddo, "On structured Markov decision processes in continuous state
space," Research Report RJ 10264, IBM Almaden Research Center, San Jose,
CA, 2000.

86.
J.
Rao, C. Zhang, G. M. Lohman, and N. Megiddo, "Automating
Physical Database Design in a Parallel Database: The DB2 Partitioning Advisor,"
Research Report RJ 10208, IBM Almaden Research Center, San Jose, CA, 2001.

87.
J.
Rao, C. Zhang, G. M. Lohman, and N. Megiddo, "Automating
Physical Database Design in a Parallel Database," Research Report RJ
10225, IBM Almaden Research Center, San Jose, CA, 2001.

88.
F.
Naumann, C. T. Ho, X. Tian,
L. Haas and N. Megiddo "Attribute
Classification Using Feature Analysis," Research Report RJ 10264, IBM
Almaden Research Center, San Jose, CA, 2002.

89.
N.
Megiddo and D. S. Modha, "A
Simple Adaptive Cache Algorithm Outperforms LRU," Research Report RJ
10284, IBM Almaden Research Center, San Jose, CA, 2003.

90.
N.
Megiddo, "Formation
of Preferences and Strategic Analysis: Can they be De-Coupled?"
9/24/2003. Presented at IMGTA'2001- XIV Italian Meeting on Game Theory and
Applications (Research
Report RJ 10218, IBM Almaden Research Center, San Jose, CA, 2001.)

91.
N.
Megiddo and D. S. Modha, "One
Up on LRU," Research Report RJ 10285, IBM Almaden Research Center, San
Jose, CA, 2003.

92.
H.
Jin, J. Lotspiech, and N. Megiddo, "Efficient Traitor Tracing," Research Report RJ 10390, IBM Almaden Research
Center, San Jose, CA, 10/03/2006.

93.
N.
Megiddo and V.V. Vazirani, "Continuity
Properties of Equilibrium Prices and Allocations in Linear Fisher Markets,"
Research Report RJ 10411, IBM Almaden Research Center, San Jose, CA, 8/24/2007

94.
E.
Hazan and N. Megiddo, "Online Learning with Prior Knowledge," Research Report 10412, IBM Almaden Research
Center, San Jose, CA, 8/24/2007.

95.
E.
Hazan and N. Megiddo, "The
"Arrangement Method" for Linear Programming is Equivalent to the
Phase-One Method," Research Report RJ 10414, IBM Almaden Research Center,
San Jose, CA, 8/28/2007.

96.
S.
Agrawal, N. Megiddo and B. Armbruster, "Equilibrium
in Prediction Markets with Buyers and Sellers," Research Report RJ
10453, IBM Almaden Research Center, San Jose, CA 10/1/2009.

97.
N.
Megiddo, "Towards
a formal analysis of emotions in games," Research Report RJ 10474, IBM
Almaden Research Center, San Jose, CA, 10/22/2010.

98.
N.
Megiddo, "Utility
Functions in Repeated Games," Research Report RJ
10492, IBM
Almaden Research Center, San Jose, CA, 11/7/2011.

99.
N.
Megiddo, "Reexamination
of Allais' Paradox, Prospect Theory, and Expected Utility Theory," Research Report RJ
10493, IBM
Almaden Research Center, San Jose, CA, 11/7/2011.

100. N. Megiddo, "SVM
Computation in a Distributed Database," Research Report RJ 10524,
IBM Almaden Research Center, San Jose, CA, 10/2/2014.

101. M. Hardt, N. Megiddo, C. H..Papadimitriou and M. Wootters, "Strategic
Classification", arXiv.org>cs>arXiv:1506.06980, 6/23 2015

102. A. Floratou, N. Megiddo, N. Potti,
F. Ozcan, U. Kale and J. Schmitz-Hermes, "Adaptive
Caching Algorithms for Big Data Systems", Research Report RJ
10531, IBM Almaden Research Center, San Jose, CA, September 2015..

*Tree Network and Planar
Rectilinear Location Theory*. By A. J. W. Kolen., *SIAM Review*
**30** (1988), No. 2, pp. 340-341.

- "HIGH-SPEED DICTIONARY EXPANSION" (with K. L.
Clarkson, D. Gruhl and N. R. Lewis), U.S.
9,348,806, 5/24/2016.
- "OPTIMIZING USER SELECTION FOR PERFORMING TASKS IN
SOCIAL NETWORKS
`"`(with J. Mahmud, M. Zhou and J. Nichols), U.S. 9,299,115, 3/29/2016. - "OPTIMIZING USER SELECTION FOR PERFORMING TASKS IN
SOCIAL NETWORKS
`"`(with J. Mahmud, M. Zhou and J. Nichols), U.S. 9,026,541, 5/5/2015. - "
`SYSTEM AND METHOD FOR GATHERING, INDEXING, AND SUPPLYING PUBLICLY AVAILABLE DATA CHARTS"`(with S. Vaithynathan) U.S. 8,799,772, 8/5/2014. - "METHOD FOR DYNAMICALLY FREEING COMPUTER RESOURCES"
(with A. Amir) U.S. 8,776,078, 7/8/2014.
- "BUFFERED VIEWING OF ELECTRONIC DOCUMENTS" (with A.
Amir), U.S. 8,707,251, 4/22/2014.
- "SYSTEM FOR RECOVERING A BARCODE" (with M. Flickner and C.A. Mildebrandt),
U.S. 8,550,359, 10/8/2013.
`"`FAST ADAPTATION IN REAL-TIME SYSTEMS`"`(with E. Hazan), U.S. 8,494,994, 7/23/2013.`"`METHOD AND APPARATUS FOR COLLABORATIVE SELECTION OF PROPOSALS`", U.S. 8,489,443, 7/16/2013.`

`"`A METHOD FOR AUTHENTICATING TELEPHONE CALLERS AND AVOIDING UNWANTED CALLS" (with A. Amir), U.S. 8,467,512, 6/18/2013.`"``SELECTIVITY ESTIMATION FOR CONJUNCTIVE PREDICATES IN THE PRESENCE OF PARTIAL KNOWLEDGE ABOUT MULTIVARIATE DISTRIBUTIONS" (with M.Kutsch, V.M. Markl and T.M.D. Tran)) U.S. 8,135,701, 3/13/2012.``"ADAPTIVE TRAITOR TRACING" (with H. Jin, J. Lotspiech, and M.J. Nelson), U.S. 8,108,928, 1/31/2012.`- "COMPUTER SYSTEM MANAGEMENT AND THROUGHPUT MAXIMIZATION
IN THE PRESENCE OF POWER CONSTRAINTS" (with R. Krauthgamer)
U.S. 8,046,605, 10/25/2011.
- "SYSTEM
AND METHOD FOR AUTOMATING DATA PARTITIONING IN A PARALLEL DATABASE"
(with G. Lohman, J. Rao and C. Zhang) U.S.
8,001,109, 8/16/2011.
`"`AUTOMATICALLY AND ADAPTIVELY DETERMINING EXECUTION PLANS FOR QUERIES WITH PARAMETER MARKERS`"`(with W. Fan, G. Lohman, V. Markl, J. Rao, and D. Simmen), U.S. 7,958,113, 6/7/2011.`"`Method for machine learning using online convex optimization problem solving with minimum regret`" (with E. Hazan), U.S. 7,870,082, 1/11/2011.``"`SYSTEM FOR ENHANCING BUYERS PERFORMANCE IN ELECTRONIC COMMERCE", U.S. 7,765,140, 7/27/2010.- "Method of developing solutions for online
convex optimization problems when a decision maker has knowledge of all
past states and resulting cost functions for previous choices and attempts
to make new choices resulting in minimal regret" (with E. Hazan), U.S. 7,730,000, 6/1/2010.
- "SYSTEM
AND METHOD FOR AUTONOMIC OPTIMIZATION BY COMPUTER PROGRAMS", U.S.
7,689,978, 3/30/2010.
`"`METHOD FOR OPERATING AND MANAGING A RE-FUELING BUSINESS`", U.S. 7,673,657, 3/9/2010.``"`METHOD FOR OPERATING AND MANAGING A RE-FUELING BUSINESS`", U.S. 7,661,446, 2/16/2010.`- "COMPUTER
SYSTEM MANAGEMENT AND THROUGHPUT MAXIMIZATION UNDER PEAK POWER CONSTRAINTS
`"`(with R. Krauthgamer), U.S. 7,587,621, 9/8/2009. - "SYSTEM AND METHOD FOR AUTOMATING DATA PARTITIONING IN A
PARALLEL DATABASE" (with G. Lohman, J. Rao
and C. Zhang) U.S. 7,562,090, 7/14/2009.
`"`METHOD FOR CREATING AND MAINTAINING THREADS OF PHONE/EMAIL/FAX/SMS CONVERSATIONS`" (with A. Amir), U.S. 7,539,295, 5/26/2009.``"`CONSISTENT AND UNBIASED CARDINALITY ESTIMATION FOR COMPLEX QUERIES WITH CONJUNCTS OF PREDICATES" (with P. Haas, M. Kutsch, and V. Markl), U.S. 7,512,629, 3/31/2009.`"`CONSISTENT HISTOGRAM MAINTENANCE USING QUERY FEEDBACK`"`(with P. Haas, V. Markl and U. Srivastava), U.S. 7,512,574, 3/31/2009.`"``COMPUTER AUTOMATED DISCOVERY OF INTERESTINGNESS IN FACETED SEARCH (with D. Dash, G. M. Lohman, and J. Rao) U.S. 7,493,319, 2/17/2009.``"`SYSTEM, METHOD AND PROGRAM PRODUCT FOR AUTOMATICALLY MANAGING CONTRACTS`", U.S. 7,480,621, 1/20/2009.``"`DISCOVERING INTERESTINGNESS IN ADVANCED FACETED SEARCH`" (with D. Dash,``G`. Lohman, and J. Rao) U.S. 7,392,250, 6/24/2008.- "SELECTIVITY
ESTIMATION FOR CONJUNCTIVE PREDICATES IN THE PRESENCE OF PARTIAL KNOWLEDGE
ABOUT MULTIVARIATE DATA DISTRIBUTIONS" (with M. Kutsch,
V. Markl, and T.M. Tran), U.S. 7,376,639,
5/20/2008.
`"METHOD AND SYSTEM FOR SEARCHING AND RETRIEVING DOCUMENTS" (with A. Tomkins and S. Vaithyanathan),`U.S. 7,209,913, 4/24/2007.

- "SYSTEM AND METHOD FOR ADAPTIVELY MANAGING PAGES IN A
MEMORY" (with D. MODHA), U.S. 7,167,953, 1/23/2007.
`"METHOD FOR SOLVING STOCHASTIC CONTROL PROBLEMS OF LINEAR SYSTEMS IN HIGH DIMENSION", U.S.`7,117,130, 10/3/2006.- "MASSIVLEY
COMPUTATIONAL PARALLIZABLE OPTIMIZATION MANAGEMENT SYSTEM AND
METHOD", U.S. 7,013,344, 3/14/2006.
`"SYSTEM AND METHOD FOR IMPLEMENTING AN ADAPTIVE REPLACEMENT CACHE POLICY" (with D. MODHA), U.S. 6,996,676, 2/7/2006`.`"SYSTEM AND METHOD FOR GATHERING, INDEXING, AND SUPPLYING PUBLICLY AVAILABLE DATA CHARTS" (with S. Vaithyanathan), U.S. 6,996,268, 2/7/2006.``"SYSTEM, METHOD AND PROGRAM PRODUCT FOR AUTOMATICALLY MANAGING CONTRACTS", U.S. 6,985,868 B1, 1/10/2006.``"EFFICIENT RETRIEVAL OF UNIFORM RESOURCE LOCATORS" (with K. McCurley), U.S. 6,957,224, 10/18/2005.``"METHOD FOR ASSIGNING ENCRYPTION KEYS" (with D. Naor, J. B. Lotspiech, S. Naor and R. Fagin), U.S. 6,947,563, 9/20/2005.``"METHOD AND PROGRAM PRODUCT FOR MAINTAINING SECURITY OF PUBLICLY DISTRIBUTED INFORMATION" (with D. Modha), U.S.6,947,557, 9/20/2005.``"SYSTEM AND METHOD FOR PROFILING ACCESS TO DISK DRIVE COMMANDS BASED ON A DUAL SERVO MODE MODEL", U.S. 6,898,665, 5/24/2005.``"SYSTEM AND METHOD FOR IMPROVING THE EFFECTIVENESS OF WEB ADVERTISING" (with X. Zhu), China, ZL0113259, 1/5/2005; U.S. 6,892,181, 5/10/2005, Singapore 102634, 5/31/2005.``"METHOD AND APPARATUS FOR REPRESENTING DATABASE AND QUERY INFORMATION USING THE INTERVAL HASH TREE" (with P. Raghavan and T.F. Syeda-Mahmood), U.S. 6,757,686, 6/29/2004.``"SYSTEM FOR SECURING ELECTRONIC MAIL", U.S. 6,745,231, 6/1/2004.`- "
`RESTRUCTURING OF EXECUTABLE COMPUTER CODE AND LARGE DATA SETS" (with B. Mendelson), U.S. 6,742,179, 5/25/2004.` `"SYSTEM AND METHOD FOR MAINTAINING MULTIPLE IDENTITIES AND REPUTATIONS FOR INTERNET INTERACTIONS", U.S. 6,725,269, 4/20/2004.`- "METHOD
FOR SOLVING A LARGE SPARSE TRIANGULAR SYSTEM OF LINEAR EQUATIONS"
(with J.J. Forrest and J.A. Tomlin), U.S. 6,694,343, 2/17/2004.
`"DIGITAL PEN USING SPECKLE TRACKING" (with R. Fagin, R.J.T. Morris, S. Rajagopalan, H.J. Rosen and T.G. Zimmerman), U.S. 6,686,579, 2/3/2004.``"SMOOTH END OF AUCTION ON THE INTERNET", U.S. 6,665,649, 12/16/2003.``"SYSTEM, METHOD AND PROGRAM PRODUCT FOR SOFTWARE DEVELOPMENT" (with X. Zhu), U.S. 6,658,642, 12/3/2003.``"NON-INTERFERING SEEK BEHAVIOR MODIFICATION FOR IMPROVED HARD DRIVE PERFORMANCE" (with S.W. Ng), U.S. 6,658,535, 12/2/2003.``"SYSTEM AND METHOD FOR SCHEDULING DISK DRIVE COMMANDS BY EXPECTED TOTAL ACCESS TIME", U.S. 6,574,676, 6/3/2003.``"SYSTEM AND METHOD FOR GROUPING DISK ACCESS COMMANDS IN A QUEUE ACCORDING TO PROXIMATE DISK POSITIONS", U.S. 6,571,298, 5/27/2003.``"SYSTEM AND METHODOLOGY FOR VIDEO CONFERENCING AND INTERNET CHATTING IN A COCKTAIL PARTY STYLE", U.S. 6,559,863, 5/6/2003.``"SYSTEM AND METHOD FOR DISCOVERING PREDICTIVE ASSOCIATION RULES" (with R. Srikant), U.S. 6,182,070, 1/30/2001.``"METHOD FOR COMPUTING NEAR NEIGHBORS OF A QUERY POINT IN A DATABASE" (with U. Shaft), U.S. 6,148,295, 11/14/2000.``"METHOD OF, SYSTEM FOR, AND COMPUTER PROGRAM PRODUCT FOR PERFORMING WEIGHTED LOOP FUSION BY AN OPTIMIZING COMPILER" (with V. Sarkar), U.S. 6,058,266, 5/2/2000.``"METHOD LOOP EXECUTION TIME BY OPTIMIZING BLOCK/TILE SIZES" (with V. Sarkar), U.S. 5,953,531, 9/14/1999.``"METHOD AND SYSTEM FOR PERFORMING RANGE MAX/MIN QUERIES ON A DATA CUBE" (with C.T. Ho and R. Agrawal), U.S. 5,926,820, 7/20/1999.``"FAST QUERY SEARCH IN LARGE DIMENSION DATABASE" (with J. L. Hafner and E. Upfal), U.S. 5,848,404, 12/8/1998.``"PROGRAM PRODUCT FOR DISPLAYING A LINE PASSING THROUGH A PLURALITY OF BOXES", U.S. 5,533,178, 7/2/1996.``"METHOD AND APPARATUS FOR DISPLAYING A LINE PASSING THROUGH A PLURALITY OF BOXES", U.S. 5,481,658, 1/2/1996.``"METHOD AND DEVICE FOR FINDING OUT LINE THROUGH AXIAL BOX IN THREE-DIMENSION AND HIGHER DIMENSION", Japan 07105403A2, 04/21/1995.`- "IDENTIFICATION
FOR PERFORMING TASKS IN OPEN SOCIAL MEDIA
`"`(with J. Mahmud, M. Zhou and J. Nichols), patent pending. - "SUPPORT VECTOR MACHINE COMPUTATION", patent
pending.
- "Host-SIDE CACHE MIGRATION" (with D. Chambliss, A. Gupta
J. L. Hafner and M. Lu, patent pending.
- "SYSTEM FOR OPTIMIZING THE PERFORMANCE OF TIERED STORAGE
SYSTEMS" (with D. Chambliss), patent pending.
- "CACHING POLICIES FOR SELECTION AND REPLACEMENT OF
OBJECTS" (with A. Floratou, U. Kale and F. Ozcan), patent pending.

*Last updated
May 31, 2016*

*English*_{}

*German *(trasnlated) _{}

*RM*_{}