×
Compute Distance To:
Author ID: nisan.noam Recent zbMATH articles by "Nisan, Noam"
Published as: Nisan, Noam; Nisan, N.
External Links: MGP · Wikidata · dblp · GND · IdRef
all top 5

Co-Authors

9 single-authored
14 Dobzinski, Shahar
14 Wigderson, Avi
11 Babaioff, Moshe
7 Blumrosen, Liad
6 Gonczarowski, Yannai A.
6 Lavi, Ron
5 Linial, Nathan
4 Goldreich, Oded
4 Impagliazzo, Russell
4 Mansour, Yishay
4 Ron, Dana
4 Schapira, Michael
3 Feldman, Michal
3 Hart, Sergiu
3 Kremer, Ilan
3 Kushilevitz, Eyal
3 Mu’alem, Ahuva
3 Naor, Moni
3 Parnas, Michal
3 Ronen, Amir
3 Rudich, Steven
3 Segal, Ilya R.
3 Ta-Shma, Amnon
3 Zuckerman, David
2 Babai, László
2 Bro Miltersen, Peter
2 Dolev, Danny
2 Feldman, David Victor
2 Fortnow, Lance J.
2 Harari, Yuval
2 Levin, Leonid A.
2 Luby, Michael G.
2 Oren, Sigal
2 Ostrovsky, Rafail
2 Rosenbaum, Will
2 Roughgarden, Tim
2 Safra, Muli
2 Saks, Michael E.
2 Shamir, Adi
2 Szegedy, Mario
2 Vishkin, Uzi
1 Abraham, Ittai
1 Aharonov, Dorit
1 Avigad, Lidor
1 Babichenko, Yakov
1 Badanidiyuru, Ashwinkumar
1 Bar-Yossef, Ziv
1 Bellare, Mihir
1 Bikhchandani, Sushil
1 Brakerski, Zvika
1 Chatterji, Shurojit
1 Dughmi, Shaddin
1 Even, Guy
1 Feder, Tomás
1 Friedgut, Ehud
1 Fu, Hu
1 Gavoille, Cyril
1 Goldwasser, Shafi
1 Gopalan, Parikshit
1 Halevi, Shai
1 Han, Li
1 Kahn, Jeff D.
1 Kalai, Gil
1 Karchmer, Mauricio
1 Karger, David R.
1 Karloff, Howard J.
1 Karp, Richard Manning
1 Kaufman, Tali
1 Keller, Nathan
1 Kitaev, Alexei Yu.
1 Kleinberg, Robert D.
1 Lehmann, Benny
1 Lehmann, Daniel J.
1 Lucier, Brendan
1 Lund, Carsten
1 Malkhi, Dahlia
1 Motwani, Rajeev
1 Mundel, Ruty
1 Pavlov, Elan
1 Sen, Arunava
1 Servedio, Rocco A.
1 Soroker, Danny
1 Sudan, Madhu
1 Szemerédi, Endre
1 Talgam-Cohen, Inbal
1 Talwar, Kunal
1 Tardos, Éva
1 Thorup, Mikkel
1 Tiwari, Prasoon
1 Trevisan, Luca
1 Vadhan, Salil P.
1 Vazirani, Vijay V.
1 Velickovic, Boban
1 Winter, Eyal

Publications by Year

Citations contained in zbMATH Open

103 Publications have been cited 2,836 times in 1,998 Documents Cited by Year
Communication complexity. Zbl 0869.68048
Kushilevitz, Eyal; Nisan, Noam
334
1997
Algorithmic game theory. Foreword by Christos H. Papadimitriou. Zbl 1130.91005
202
2007
Hardness vs randomness. Zbl 0821.68057
Nisan, Noam; Wigderson, Avi
160
1994
Pseudorandom generators for space-bounded computation. Zbl 0759.68024
Nisan, Noam
115
1992
Combinatorial auctions with decreasing marginal utilities. Zbl 1125.91043
Lehmann, Benny; Lehmann, Daniel; Nisan, Noam
107
2006
Constant depth circuits, Fourier transform, and learnability. Zbl 0781.94006
Linial, Nathan; Mansour, Yishay; Nisan, Noam
102
1993
Algorithmic mechanism design. Zbl 0996.68251
Nisan, Noam; Ronen, Amir
100
2001
Algebraic methods for interactive proof systems. Zbl 0799.68097
Lund, Carsten; Fortnow, Lance; Karloff, Howard; Nisan, Noam
95
1992
Randomness is linear in space. Zbl 0846.68041
Nisan, Noam; Zuckerman, David
87
1996
On the degree of Boolean functions as real polynomials. Zbl 0829.68047
Nisan, Noam; Szegedy, Mario
72
1994
Quantum circuits with mixed states. Zbl 1028.68054
Aharonov, Dorit; Kitaev, Alexei; Nisan, Noam
62
1998
Algorithmic mechanism design (extended abstract). Zbl 1346.68246
Nisan, Noam; Ronen, Amir
59
1999
\(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs. Zbl 0802.68054
Babai, László; Fortnow, Lance; Nisan, Noam; Wigderson, Avi
55
1993
Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs. Zbl 0769.68040
Babai, László; Nisan, Noam; Szegedy, Márió
48
1992
CREW PRAMs and decision trees. Zbl 0737.68028
Nisan, Noam
47
1991
Computationally feasible VCG mechanisms. Zbl 1165.91387
Nisan, N.; Ronen, A.
46
2007
Introduction to mechanism design (for computer scientists). Zbl 1143.91323
Nisan, Noam
45
2007
Weak monotonicity characterizes deterministic dominant-strategy implementation. Zbl 1152.91428
Bikhchandani, Sushil; Chatterji, Shurojit; Lavi, Ron; Mu’alem, Ahuva; Nisan, Noam; Sen, Arunava
44
2006
Multi-unit auctions with budget limits. Zbl 1279.91080
Dobzinski, Shahar; Lavi, Ron; Nisan, Noam
43
2012
Lower bounds on arithmetic circuits via partial derivatives. Zbl 0890.68074
Nisan, Noam; Wigderson, Avi
41
1997
The communication requirements of efficient allocations and supporting prices. Zbl 1132.91531
Nisan, Noam; Segal, Ilya
39
2006
Approximate inclusion-exclusion. Zbl 0738.05009
Linial, Nathan; Nisan, Noam
38
1990
Pseudorandom bits for constant depth circuits. Zbl 0732.68056
Nisan, Noam
37
1991
Pseudorandomness for network algorithms. Zbl 1345.68269
Impagliazzo, Russell; Nisan, Noam; Wigderson, Avi
34
1994
On rank vs. communication complexity. Zbl 0845.68038
Nisan, Noam; Wigderson, Avi
31
1995
Approximate revenue maximization with multiple items. Zbl 1414.91151
Hart, Sergiu; Nisan, Noam
30
2017
A parallel approximation algorithm for positive linear programming. Zbl 1310.68224
Luby, Michael; Nisan, Noam
29
1993
On data structures and asymmetric communication complexity. Zbl 0920.68042
Miltersen, Peter Bro; Nisan, Noam; Safra, Shmuel; Wigderson, Avi
28
1998
On randomized one-round communication complexity. Zbl 0942.68059
Kremer, Ilan; Nisan, Noam; Ron, Dana
28
1999
On the cover time of random walks on graphs. Zbl 0681.60064
Kahn, Jeff D.; Linial, Nathan; Nisan, Noam; Saks, Michael E.
28
1989
The communication complexity of threshold gates. Zbl 0790.94028
Nisan, N.
27
1993
Rounds in communication complexity revisited. Zbl 0767.68066
Nisan, Noam; Wigderson, Avi
25
1993
On Yao’s XOR-lemma. Zbl 1304.68074
Goldreich, Oded; Nisan, Noam; Wigderson, Avi
24
2011
Truthful randomized mechanisms for combinatorial auctions. Zbl 1300.91033
Dobzinski, Shahar; Nisan, Noam; Schapira, Michael
24
2006
Combinatorial auctions. Zbl 1152.91453
Blumrosen, Liad; Nisan, Noam
21
2007
Truthful approximation mechanisms for restricted combinatorial auctions. Zbl 1152.91472
Mu’Alem, Ahuva; Nisan, Noam
20
2008
Amortized communication complexity. Zbl 0830.68070
Feder, Tomàs; Kushilevitz, Eyal; Naor, Moni; Nisan, Noam
20
1995
Approximation algorithms for combinatorial auctions with complement-free bidders. Zbl 1192.68890
Dobzinski, Shahar; Nisan, Noam; Schapira, Michael
20
2005
Competitive analysis of incentive compatible on-line auctions. Zbl 1098.91044
Lavi, Ron; Nisan, Noam
19
2004
Extracting randomness: A survey and new constructions. Zbl 0943.68190
Nisan, Noam; Ta-Shma, Amnon
18
1999
Auctions with severely bounded communication. Zbl 1165.91376
Blumrosen, L.; Nisan, N.; Segal, I.
18
2007
Fractional covers and communication complexity. Zbl 0817.68094
Karchmer, Mauricio; Kushilevitz, Eyal; Nisan, Noam
17
1995
Approximation algorithms for combinatorial auctions with complement-free bidders. Zbl 1216.68338
Dobzinski, Shahar; Nisan, Noam; Schapira, Michael
16
2010
On the computational power of demand queries. Zbl 1193.91027
Blumrosen, Liad; Nisan, Noam
15
2009
Multi-unit auctions: beyond Roberts. Zbl 1314.91118
Dobzinski, Shahar; Nisan, Noam
15
2015
Efficient approximation of product distributions. Zbl 0959.68553
Even, Guy; Goldreich, Oded; Luby, Michael; Nisan, Noam; Veličković, Boban
14
1998
Mechanisms for multi-unit auctions. Zbl 1188.91079
Dobzinski, Shahar; Nisan, Noam
14
2010
On randomized one-round communication complexity. Zbl 0926.94022
Kremer, Ilan; Nisan, Noam; Ron, Dana
14
1995
Two simplified proofs for Roberts’ theorem. Zbl 1187.91059
Lavi, Ron; Mu’alem, Ahuva; Nisan, Noam
13
2009
The effect of random restrictions on formula size. Zbl 0771.68065
Impagliazzo, Russell; Nisan, Noam
13
1993
Symmetric logspace is closed under complement. Zbl 0978.68525
Nisan, Noam; Ta-Shma, Amnon
13
1995
The computational complexity of universal hashing. Zbl 0764.68080
Mansour, Yishay; Nisan, Noam; Tiwari, Prasoon
13
1993
\(\text{RL}\subseteq \text{SC}\). Zbl 0806.68043
Nisan, Noam
12
1994
The query complexity of correlated equilibria. Zbl 1400.91006
Hart, Sergiu; Nisan, Noam
12
2018
Truthful randomized mechanisms for combinatorial auctions. Zbl 1237.91114
Dobzinski, Shahar; Nisan, Noam; Schapira, Michael
12
2012
The communication complexity of approximate set packing and covering. Zbl 1057.68645
Nisan, Noam
10
2002
Products and help bits in decision trees. Zbl 0918.68026
Nisan, Noam; Rudich, Steven; Saks, Michael
10
1999
The menu-size complexity of revenue approximation. Zbl 1369.68227
Babaioff, Moshe; Gonczarowski, Yannai A.; Nisan, Noam
10
2017
Compact name-independent routing with minimum stretch. Zbl 1445.68143
Abraham, Ittai; Gavoille, Cyril; Malkhi, Dahlia; Nisan, Noam; Thorup, Mikkel
10
2008
A quantitative version of the Gibbard-Satterthwaite theorem for three alternatives. Zbl 1229.05264
Friedgut, Ehud; Kalai, Gil; Keller, Nathan; Nisan, Noam
9
2011
On read-once vs. multiple access to randomness in logspace. Zbl 0774.68037
Nisan, Noam
9
1993
Concurrent auctions across the supply chain. Zbl 1080.68727
Babaioff, Moshe; Nisan, Noam
8
2004
On data structures and asymmetric communication complexity. Zbl 0968.68507
Miltersen, Peter Bro; Nisan, Noam; Safra, Shmuel; Wigderson, Avi
8
1995
Combinatorial agency. Zbl 1258.91082
Babaioff, Moshe; Feldman, Michal; Nisan, Noam; Winter, Eyal
8
2012
Online ascending auctions for gradually expiring items. Zbl 1297.91083
Lavi, Ron; Nisan, Noam
8
2005
Sketching valuation functions. Zbl 1422.91290
Badanidiyuru, Ashwinkumar; Dobzinski, Shahar; Fu, Hu; Kleinberg, Robert; Nisan, Noam; Roughgarden, Tim
7
2012
Sampling and representation complexity of revenue maximization. Zbl 1406.91171
Dughmi, Shaddin; Han, Li; Nisan, Noam
7
2014
Competitive equilibrium with indivisible goods and generic budgets. Zbl 1466.91138
Babaioff, Moshe; Nisan, Noam; Talgam-Cohen, Inbal
6
2021
A modular approach to Roberts’ theorem. Zbl 1253.91061
Dobzinski, Shahar; Nisan, Noam
6
2009
Undirected connectivity in \(O(\log^{1. 5} n)\) space. Zbl 0915.05081
Nisan, Noam; Szemeredi, Endre; Wigderson, Avi
6
1992
Informational limitations of ascending combinatorial auctions. Zbl 1245.91035
Blumrosen, Liad; Nisan, Noam
6
2010
Limitations of VCG-based mechanisms. Zbl 1232.91290
Dobzinski, Shahar; Nisan, Noam
5
2007
Smooth Boolean functions are easy: efficient algorithms for low-sensitivity functions. Zbl 1334.68068
Gopalan, Parikshit; Nisan, Noam; Servedio, Rocco A.; Talwar, Kunal; Wigderson, Avi
5
2016
Free-riding and free-labor in combinatorial agency. Zbl 1262.91102
Babaioff, Moshe; Feldman, Michal; Nisan, Noam
5
2009
On constructing 1-1 one-way functions. Zbl 1343.94056
Goldreich, Oded; Levin, Leonid A.; Nisan, Noam
5
2011
On the complexity of bilinear forms, dedicated to the memory of Jacques Morgenstern. Zbl 1059.68577
Nisan, Noam; Wigderson, Avi
5
1995
Mechanisms for a spatially distributed market. Zbl 1165.91374
Babaioff, Moshe; Nisan, Noam; Pavlov, Elan
5
2009
Limitations of VCG-based mechanisms. Zbl 1299.91048
Dobzinski, Shahar; Nisan, Noam
5
2011
Selling multiple correlated goods: revenue maximization and menu-size complexity. Zbl 1422.91307
Hart, Sergiu; Nisan, Noam
5
2019
The communication complexity of local search. Zbl 1433.68143
Babichenko, Yakov; Dobzinski, Shahar; Nisan, Noam
4
2019
Multi-player and multi-round auctions with severely bounded communication. Zbl 1266.91031
Blumrosen, Liad; Nisan, Noam; Segal, Ilya
4
2003
Fast connected components algorithms for the EREW PRAM. Zbl 0918.68042
Karger, David R.; Nisan, Noam; Parnas, Michal
4
1999
More deterministic simulation in logspace. Zbl 1310.68116
Nisan, Noam; Zuckerman, David
4
1993
Economic efficiency requires interaction. Zbl 1315.91027
Dobzinski, Shahar; Nisan, Noam; Oren, Sigal
4
2014
Efficient empirical revenue maximization in single-parameter auction environments. Zbl 1370.68252
Gonczarowski, Yannai A.; Nisan, Noam
4
2017
A stable marriage requires communication. Zbl 1372.68125
Gonczarowski, Yannai A.; Nisan, Noam; Ostrovsky, Rafail; Rosenbaum, Will
4
2015
Lower bounds on arithmetic circuits via partial derivatives. (Preliminary version). Zbl 0938.68646
Nisan, Noam; Wigderson, Avi
3
1995
Mixed strategies in combinatorial agency. Zbl 1210.68119
Babaioff, M.; Feldman, M.; Nisan, N.
3
2010
Probabilistic analysis of network flow algorithms. Zbl 0780.90039
Karp, Richard M.; Motwani, Rajeev; Nisan, Noam
2
1993
Symmetric Logspace is closed under complement. Zbl 0924.68039
Nisan, Noam; Ta-Shma, Amnon
2
1995
Correlated and coarse equilibria of single-item auctions. Zbl 1406.91173
Feldman, Michal; Lucier, Brendan; Nisan, Noam
2
2016
Online ascending auctions for gradually expiring items. Zbl 1314.91123
Lavi, Ron; Nisan, Noam
2
2015
On dice and coins: Models of computation for random generation. Zbl 0772.68036
Feldman, David; Impagliazzo, Russell; Naor, Moni; Nisan, Noam; Rudich, Steven; Shamir, Adi
1
1993
Pointer jumping requires concurrent read. Zbl 0963.68003
Nisan, Noam; Bar-Yossef, Ziv
1
1999
Neighborhood preserving hashing and approximate queries. Zbl 0873.68034
Dolev, Danny; Harari, Yuval; Linial, Nathan; Nisan, Noam; Parnas, Michal
1
1994
Errata for: “On randomized one-round communication complexity”. Zbl 1039.68553
Kremer, Ilan; Nisan, Noam; Ron, Dana
1
2001
Trade-offs between communication throughput and parallel time. Zbl 1344.68032
Mansour, Yishay; Nisan, Noam; Vishkin, Uzi
1
1994
On dice and coins: Models of computation for random generation. Zbl 0682.68073
Feldman, David; Impagliazzo, Russell; Naor, Moni; Nisan, Noam; Rudich, Steven; Shamir, Adi
1
1989
Neighborhood preserving hashing and approximate queries. Zbl 0992.68051
Dolev, Danny; Harari, Yuval; Linial, Nathan; Nisan, Noam; Parnas, Michal
1
2001
Google’s auction for TV ads. Zbl 1288.91112
Nisan, Noam
1
2010
Competitive equilibrium with indivisible goods and generic budgets. Zbl 1466.91138
Babaioff, Moshe; Nisan, Noam; Talgam-Cohen, Inbal
6
2021
Selling multiple correlated goods: revenue maximization and menu-size complexity. Zbl 1422.91307
Hart, Sergiu; Nisan, Noam
5
2019
The communication complexity of local search. Zbl 1433.68143
Babichenko, Yakov; Dobzinski, Shahar; Nisan, Noam
4
2019
Economic efficiency requires interaction. Zbl 1429.91172
Dobzinski, Shahar; Nisan, Noam; Oren, Sigal
1
2019
A stable marriage requires communication. Zbl 1429.91232
Gonczarowski, Yannai A.; Nisan, Noam; Ostrovsky, Rafail; Rosenbaum, Will
1
2019
The query complexity of correlated equilibria. Zbl 1400.91006
Hart, Sergiu; Nisan, Noam
12
2018
Approximate revenue maximization with multiple items. Zbl 1414.91151
Hart, Sergiu; Nisan, Noam
30
2017
The menu-size complexity of revenue approximation. Zbl 1369.68227
Babaioff, Moshe; Gonczarowski, Yannai A.; Nisan, Noam
10
2017
Efficient empirical revenue maximization in single-parameter auction environments. Zbl 1370.68252
Gonczarowski, Yannai A.; Nisan, Noam
4
2017
Smooth Boolean functions are easy: efficient algorithms for low-sensitivity functions. Zbl 1334.68068
Gopalan, Parikshit; Nisan, Noam; Servedio, Rocco A.; Talwar, Kunal; Wigderson, Avi
5
2016
Correlated and coarse equilibria of single-item auctions. Zbl 1406.91173
Feldman, Michal; Lucier, Brendan; Nisan, Noam
2
2016
Multi-unit auctions: beyond Roberts. Zbl 1314.91118
Dobzinski, Shahar; Nisan, Noam
15
2015
A stable marriage requires communication. Zbl 1372.68125
Gonczarowski, Yannai A.; Nisan, Noam; Ostrovsky, Rafail; Rosenbaum, Will
4
2015
Online ascending auctions for gradually expiring items. Zbl 1314.91123
Lavi, Ron; Nisan, Noam
2
2015
Sampling and representation complexity of revenue maximization. Zbl 1406.91171
Dughmi, Shaddin; Han, Li; Nisan, Noam
7
2014
Economic efficiency requires interaction. Zbl 1315.91027
Dobzinski, Shahar; Nisan, Noam; Oren, Sigal
4
2014
Multi-unit auctions with budget limits. Zbl 1279.91080
Dobzinski, Shahar; Lavi, Ron; Nisan, Noam
43
2012
Truthful randomized mechanisms for combinatorial auctions. Zbl 1237.91114
Dobzinski, Shahar; Nisan, Noam; Schapira, Michael
12
2012
Combinatorial agency. Zbl 1258.91082
Babaioff, Moshe; Feldman, Michal; Nisan, Noam; Winter, Eyal
8
2012
Sketching valuation functions. Zbl 1422.91290
Badanidiyuru, Ashwinkumar; Dobzinski, Shahar; Fu, Hu; Kleinberg, Robert; Nisan, Noam; Roughgarden, Tim
7
2012
On Yao’s XOR-lemma. Zbl 1304.68074
Goldreich, Oded; Nisan, Noam; Wigderson, Avi
24
2011
A quantitative version of the Gibbard-Satterthwaite theorem for three alternatives. Zbl 1229.05264
Friedgut, Ehud; Kalai, Gil; Keller, Nathan; Nisan, Noam
9
2011
On constructing 1-1 one-way functions. Zbl 1343.94056
Goldreich, Oded; Levin, Leonid A.; Nisan, Noam
5
2011
Limitations of VCG-based mechanisms. Zbl 1299.91048
Dobzinski, Shahar; Nisan, Noam
5
2011
Approximation algorithms for combinatorial auctions with complement-free bidders. Zbl 1216.68338
Dobzinski, Shahar; Nisan, Noam; Schapira, Michael
16
2010
Mechanisms for multi-unit auctions. Zbl 1188.91079
Dobzinski, Shahar; Nisan, Noam
14
2010
Informational limitations of ascending combinatorial auctions. Zbl 1245.91035
Blumrosen, Liad; Nisan, Noam
6
2010
Mixed strategies in combinatorial agency. Zbl 1210.68119
Babaioff, M.; Feldman, M.; Nisan, N.
3
2010
Google’s auction for TV ads. Zbl 1288.91112
Nisan, Noam
1
2010
On the computational power of demand queries. Zbl 1193.91027
Blumrosen, Liad; Nisan, Noam
15
2009
Two simplified proofs for Roberts’ theorem. Zbl 1187.91059
Lavi, Ron; Mu’alem, Ahuva; Nisan, Noam
13
2009
A modular approach to Roberts’ theorem. Zbl 1253.91061
Dobzinski, Shahar; Nisan, Noam
6
2009
Free-riding and free-labor in combinatorial agency. Zbl 1262.91102
Babaioff, Moshe; Feldman, Michal; Nisan, Noam
5
2009
Mechanisms for a spatially distributed market. Zbl 1165.91374
Babaioff, Moshe; Nisan, Noam; Pavlov, Elan
5
2009
Truthful approximation mechanisms for restricted combinatorial auctions. Zbl 1152.91472
Mu’Alem, Ahuva; Nisan, Noam
20
2008
Compact name-independent routing with minimum stretch. Zbl 1445.68143
Abraham, Ittai; Gavoille, Cyril; Malkhi, Dahlia; Nisan, Noam; Thorup, Mikkel
10
2008
Algorithmic game theory. Foreword by Christos H. Papadimitriou. Zbl 1130.91005
202
2007
Computationally feasible VCG mechanisms. Zbl 1165.91387
Nisan, N.; Ronen, A.
46
2007
Introduction to mechanism design (for computer scientists). Zbl 1143.91323
Nisan, Noam
45
2007
Combinatorial auctions. Zbl 1152.91453
Blumrosen, Liad; Nisan, Noam
21
2007
Auctions with severely bounded communication. Zbl 1165.91376
Blumrosen, L.; Nisan, N.; Segal, I.
18
2007
Limitations of VCG-based mechanisms. Zbl 1232.91290
Dobzinski, Shahar; Nisan, Noam
5
2007
Combinatorial auctions with decreasing marginal utilities. Zbl 1125.91043
Lehmann, Benny; Lehmann, Daniel; Nisan, Noam
107
2006
Weak monotonicity characterizes deterministic dominant-strategy implementation. Zbl 1152.91428
Bikhchandani, Sushil; Chatterji, Shurojit; Lavi, Ron; Mu’alem, Ahuva; Nisan, Noam; Sen, Arunava
44
2006
The communication requirements of efficient allocations and supporting prices. Zbl 1132.91531
Nisan, Noam; Segal, Ilya
39
2006
Truthful randomized mechanisms for combinatorial auctions. Zbl 1300.91033
Dobzinski, Shahar; Nisan, Noam; Schapira, Michael
24
2006
Approximation algorithms for combinatorial auctions with complement-free bidders. Zbl 1192.68890
Dobzinski, Shahar; Nisan, Noam; Schapira, Michael
20
2005
Online ascending auctions for gradually expiring items. Zbl 1297.91083
Lavi, Ron; Nisan, Noam
8
2005
Competitive analysis of incentive compatible on-line auctions. Zbl 1098.91044
Lavi, Ron; Nisan, Noam
19
2004
Concurrent auctions across the supply chain. Zbl 1080.68727
Babaioff, Moshe; Nisan, Noam
8
2004
Multi-player and multi-round auctions with severely bounded communication. Zbl 1266.91031
Blumrosen, Liad; Nisan, Noam; Segal, Ilya
4
2003
The communication complexity of approximate set packing and covering. Zbl 1057.68645
Nisan, Noam
10
2002
Algorithmic mechanism design. Zbl 0996.68251
Nisan, Noam; Ronen, Amir
100
2001
Errata for: “On randomized one-round communication complexity”. Zbl 1039.68553
Kremer, Ilan; Nisan, Noam; Ron, Dana
1
2001
Neighborhood preserving hashing and approximate queries. Zbl 0992.68051
Dolev, Danny; Harari, Yuval; Linial, Nathan; Nisan, Noam; Parnas, Michal
1
2001
Algorithmic mechanism design (extended abstract). Zbl 1346.68246
Nisan, Noam; Ronen, Amir
59
1999
On randomized one-round communication complexity. Zbl 0942.68059
Kremer, Ilan; Nisan, Noam; Ron, Dana
28
1999
Extracting randomness: A survey and new constructions. Zbl 0943.68190
Nisan, Noam; Ta-Shma, Amnon
18
1999
Products and help bits in decision trees. Zbl 0918.68026
Nisan, Noam; Rudich, Steven; Saks, Michael
10
1999
Fast connected components algorithms for the EREW PRAM. Zbl 0918.68042
Karger, David R.; Nisan, Noam; Parnas, Michal
4
1999
Pointer jumping requires concurrent read. Zbl 0963.68003
Nisan, Noam; Bar-Yossef, Ziv
1
1999
Quantum circuits with mixed states. Zbl 1028.68054
Aharonov, Dorit; Kitaev, Alexei; Nisan, Noam
62
1998
On data structures and asymmetric communication complexity. Zbl 0920.68042
Miltersen, Peter Bro; Nisan, Noam; Safra, Shmuel; Wigderson, Avi
28
1998
Efficient approximation of product distributions. Zbl 0959.68553
Even, Guy; Goldreich, Oded; Luby, Michael; Nisan, Noam; Veličković, Boban
14
1998
Communication complexity. Zbl 0869.68048
Kushilevitz, Eyal; Nisan, Noam
334
1997
Lower bounds on arithmetic circuits via partial derivatives. Zbl 0890.68074
Nisan, Noam; Wigderson, Avi
41
1997
Randomness is linear in space. Zbl 0846.68041
Nisan, Noam; Zuckerman, David
87
1996
On rank vs. communication complexity. Zbl 0845.68038
Nisan, Noam; Wigderson, Avi
31
1995
Amortized communication complexity. Zbl 0830.68070
Feder, Tomàs; Kushilevitz, Eyal; Naor, Moni; Nisan, Noam
20
1995
Fractional covers and communication complexity. Zbl 0817.68094
Karchmer, Mauricio; Kushilevitz, Eyal; Nisan, Noam
17
1995
On randomized one-round communication complexity. Zbl 0926.94022
Kremer, Ilan; Nisan, Noam; Ron, Dana
14
1995
Symmetric logspace is closed under complement. Zbl 0978.68525
Nisan, Noam; Ta-Shma, Amnon
13
1995
On data structures and asymmetric communication complexity. Zbl 0968.68507
Miltersen, Peter Bro; Nisan, Noam; Safra, Shmuel; Wigderson, Avi
8
1995
On the complexity of bilinear forms, dedicated to the memory of Jacques Morgenstern. Zbl 1059.68577
Nisan, Noam; Wigderson, Avi
5
1995
Lower bounds on arithmetic circuits via partial derivatives. (Preliminary version). Zbl 0938.68646
Nisan, Noam; Wigderson, Avi
3
1995
Symmetric Logspace is closed under complement. Zbl 0924.68039
Nisan, Noam; Ta-Shma, Amnon
2
1995
Hardness vs randomness. Zbl 0821.68057
Nisan, Noam; Wigderson, Avi
160
1994
On the degree of Boolean functions as real polynomials. Zbl 0829.68047
Nisan, Noam; Szegedy, Mario
72
1994
Pseudorandomness for network algorithms. Zbl 1345.68269
Impagliazzo, Russell; Nisan, Noam; Wigderson, Avi
34
1994
\(\text{RL}\subseteq \text{SC}\). Zbl 0806.68043
Nisan, Noam
12
1994
Neighborhood preserving hashing and approximate queries. Zbl 0873.68034
Dolev, Danny; Harari, Yuval; Linial, Nathan; Nisan, Noam; Parnas, Michal
1
1994
Trade-offs between communication throughput and parallel time. Zbl 1344.68032
Mansour, Yishay; Nisan, Noam; Vishkin, Uzi
1
1994
Constant depth circuits, Fourier transform, and learnability. Zbl 0781.94006
Linial, Nathan; Mansour, Yishay; Nisan, Noam
102
1993
\(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs. Zbl 0802.68054
Babai, László; Fortnow, Lance; Nisan, Noam; Wigderson, Avi
55
1993
A parallel approximation algorithm for positive linear programming. Zbl 1310.68224
Luby, Michael; Nisan, Noam
29
1993
The communication complexity of threshold gates. Zbl 0790.94028
Nisan, N.
27
1993
Rounds in communication complexity revisited. Zbl 0767.68066
Nisan, Noam; Wigderson, Avi
25
1993
The effect of random restrictions on formula size. Zbl 0771.68065
Impagliazzo, Russell; Nisan, Noam
13
1993
The computational complexity of universal hashing. Zbl 0764.68080
Mansour, Yishay; Nisan, Noam; Tiwari, Prasoon
13
1993
On read-once vs. multiple access to randomness in logspace. Zbl 0774.68037
Nisan, Noam
9
1993
More deterministic simulation in logspace. Zbl 1310.68116
Nisan, Noam; Zuckerman, David
4
1993
Probabilistic analysis of network flow algorithms. Zbl 0780.90039
Karp, Richard M.; Motwani, Rajeev; Nisan, Noam
2
1993
On dice and coins: Models of computation for random generation. Zbl 0772.68036
Feldman, David; Impagliazzo, Russell; Naor, Moni; Nisan, Noam; Rudich, Steven; Shamir, Adi
1
1993
Pseudorandom generators for space-bounded computation. Zbl 0759.68024
Nisan, Noam
115
1992
Algebraic methods for interactive proof systems. Zbl 0799.68097
Lund, Carsten; Fortnow, Lance; Karloff, Howard; Nisan, Noam
95
1992
Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs. Zbl 0769.68040
Babai, László; Nisan, Noam; Szegedy, Márió
48
1992
Undirected connectivity in \(O(\log^{1. 5} n)\) space. Zbl 0915.05081
Nisan, Noam; Szemeredi, Endre; Wigderson, Avi
6
1992
CREW PRAMs and decision trees. Zbl 0737.68028
Nisan, Noam
47
1991
Pseudorandom bits for constant depth circuits. Zbl 0732.68056
Nisan, Noam
37
1991
Approximate inclusion-exclusion. Zbl 0738.05009
Linial, Nathan; Nisan, Noam
38
1990
...and 3 more Documents
all top 5

Cited by 2,686 Authors

31 Nisan, Noam
23 Goldreich, Oded
18 Fortnow, Lance J.
16 Bollig, Beate
16 Wigderson, Avi
15 Servedio, Rocco A.
14 Feldman, Michal
14 Filmus, Yuval
14 Penna, Paolo
14 Pitassi, Toniann
13 Allender, Eric W.
13 Dobzinski, Shahar
13 Koutsoupias, Elias
13 Shaltiel, Ronen
12 Shraibman, Adi
12 Srinivasan, Srikanth
12 Viola, Emanuele
12 Yehudayoff, Amir
12 Zuckerman, David
11 Ambainis, Andris
11 Braverman, Mark
11 Chattopadhyay, Arkadev
11 Göös, Mika
11 Kabanets, Valentine
11 Meir, Or
11 Roughgarden, Tim
11 Saks, Michael E.
11 Ventre, Carmine
10 Buhrman, Harry
10 Giannakopoulos, Yiannis
10 Hromkovič, Juraj
10 Lavi, Ron
10 Lovett, Shachar
10 Markakis, Evangelos
10 van Melkebeek, Dieter
10 Williams, Richard Ryan
10 Woodruff, David P.
9 Caragiannis, Ioannis
9 de Wolf, Ronald Michiel
9 Feige, Uriel
9 Impagliazzo, Russell
9 Mossel, Elchanan
9 Müller, Rudolf
9 O’Donnell, Ryan
9 Raz, Ran
9 Santhanam, Rahul
9 Sergioli, Giuseppe
9 Sherstov, Alexander A.
9 Ta-Shma, Amnon
9 Tal, Avishay
9 Vadhan, Salil P.
8 Applebaum, Benny
8 Arvind, Vikraman
8 Chiesa, Alessandro
8 Feigenbaum, Joan
8 Giuntini, Roberto
8 Gonen, Rica
8 Jain, Rahul
8 Kleinberg, Robert D.
8 Kumar, Mrinal
8 Lee, Troy
8 Limaye, Nutan
8 Linial, Nathan
8 Mishra, Debasis
8 Parkes, David C.
8 Saptharishi, Ramprasad
8 Schnitger, Georg
8 Shioura, Akiyoshi
8 Shpilka, Amir
8 Sun, Xiaoming
8 Talgam-Cohen, Inbal
8 Vinodchandran, N. Variyam
7 Auletta, Vincenzo
7 Babaioff, Moshe
7 Blumrosen, Liad
7 Dütting, Paul
7 Ferraioli, Diodato
7 Fraigniaud, Pierre
7 Hatami, Hamed
7 Hitchcock, John M.
7 Hoza, William M.
7 Kayal, Neeraj
7 Köbler, Johannes
7 Le Gall, François
7 Lucier, Brendan
7 Nishimura, Harumichi
7 Papadimitriou, Christos Harilaos
7 Procaccia, Ariel D.
7 Rapaport, Ivan
7 Reingold, Omer
7 Saha, Chandan
7 Sauerhoff, Martin
7 Serna Iglesias, Maria José
7 Srinivasan, Aravind
7 Tennenholtz, Moshe
7 Wegener, Ingo
7 Weinberg, Seth Matthew
7 Zhang, Shengyu
6 Amano, Kazuyuki
6 Anshelevich, Elliot
...and 2,586 more Authors
all top 5

Cited in 219 Serials

179 Theoretical Computer Science
110 Journal of Computer and System Sciences
102 SIAM Journal on Computing
88 Computational Complexity
71 Theory of Computing Systems
70 Games and Economic Behavior
67 Algorithmica
59 Information Processing Letters
41 Information and Computation
31 Journal of Economic Theory
27 Artificial Intelligence
27 Journal of Cryptology
25 Distributed Computing
25 Mathematical Programming. Series A. Series B
24 Discrete Applied Mathematics
23 Combinatorica
17 Mathematics of Operations Research
17 European Journal of Operational Research
15 Operations Research
15 Random Structures & Algorithms
11 SIAM Journal on Discrete Mathematics
11 Economic Theory
11 Journal of the ACM
10 Journal of Mathematical Economics
10 Combinatorics, Probability and Computing
9 Operations Research Letters
9 International Journal of Foundations of Computer Science
9 Journal of Combinatorial Optimization
8 Social Choice and Welfare
8 RAIRO. Theoretical Informatics and Applications
8 Natural Computing
7 Mathematical Social Sciences
7 The Electronic Journal of Combinatorics
7 Annals of Mathematics and Artificial Intelligence
6 Discrete Mathematics
6 Automatica
6 Annals of Pure and Applied Logic
6 Linear Algebra and its Applications
6 Journal of High Energy Physics
5 Communications in Mathematical Physics
5 Computers & Operations Research
5 Annals of Operations Research
5 Machine Learning
5 Economics Letters
5 Journal of Global Optimization
5 Bulletin of the American Mathematical Society. New Series
5 Annals of Mathematics. Second Series
5 CEJOR. Central European Journal of Operations Research
5 OR Spectrum
5 Quantum Information Processing
4 International Journal of Theoretical Physics
4 Information Sciences
4 International Journal of Game Theory
4 The Journal of Symbolic Logic
4 Journal of Theoretical Probability
4 Journal of Mathematical Sciences (New York)
4 Constraints
4 International Game Theory Review
4 Games
4 ACM Transactions on Computation Theory
3 Israel Journal of Mathematics
3 Computing
3 Journal of Combinatorial Theory. Series A
3 European Journal of Combinatorics
3 Probability Theory and Related Fields
3 Discrete & Computational Geometry
3 Journal of Automated Reasoning
3 Journal of the American Mathematical Society
3 JETAI. Journal of Experimental & Theoretical Artificial Intelligence
3 Neural Computation
3 Japan Journal of Industrial and Applied Mathematics
3 MSCS. Mathematical Structures in Computer Science
3 Designs, Codes and Cryptography
3 Automation and Remote Control
3 SIAM Journal on Optimization
3 Electronic Journal of Probability
3 Mathematical Problems in Engineering
3 Mathematical Methods of Operations Research
3 Chicago Journal of Theoretical Computer Science
3 Journal of Scheduling
3 Discrete Mathematics and Theoretical Computer Science. DMTCS
3 Data Mining and Knowledge Discovery
3 New Journal of Physics
3 Review of Economic Design
3 Sādhanā
3 Discrete Optimization
3 Discrete Mathematics, Algorithms and Applications
3 Theory of Computing
3 Computer Science Review
2 Acta Informatica
2 International Journal of General Systems
2 Journal of Mathematical Physics
2 Journal of Statistical Physics
2 Problems of Information Transmission
2 Acta Mathematica
2 Journal of Combinatorial Theory. Series B
2 Journal of Number Theory
2 Mathematical Systems Theory
2 Transactions of the American Mathematical Society
2 Statistics & Probability Letters
...and 119 more Serials
all top 5

Cited in 41 Fields

1,280 Computer science (68-XX)
581 Game theory, economics, finance, and other social and behavioral sciences (91-XX)
289 Information and communication theory, circuits (94-XX)
261 Operations research, mathematical programming (90-XX)
191 Combinatorics (05-XX)
107 Quantum theory (81-XX)
65 Mathematical logic and foundations (03-XX)
55 Probability theory and stochastic processes (60-XX)
47 Order, lattices, ordered algebraic structures (06-XX)
36 Numerical analysis (65-XX)
32 Number theory (11-XX)
29 Linear and multilinear algebra; matrix theory (15-XX)
24 Statistics (62-XX)
13 Convex and discrete geometry (52-XX)
12 Functional analysis (46-XX)
12 Biology and other natural sciences (92-XX)
10 Field theory and polynomials (12-XX)
10 Harmonic analysis on Euclidean spaces (42-XX)
10 Systems theory; control (93-XX)
8 Group theory and generalizations (20-XX)
8 Operator theory (47-XX)
7 Commutative algebra (13-XX)
7 Algebraic geometry (14-XX)
6 Calculus of variations and optimal control; optimization (49-XX)
6 Statistical mechanics, structure of matter (82-XX)
5 Measure and integration (28-XX)
5 Approximations and expansions (41-XX)
4 General and overarching topics; collections (00-XX)
4 Functions of a complex variable (30-XX)
4 Dynamical systems and ergodic theory (37-XX)
4 Relativity and gravitational theory (83-XX)
3 Real functions (26-XX)
3 Geometry (51-XX)
2 Abstract harmonic analysis (43-XX)
2 Differential geometry (53-XX)
2 Manifolds and cell complexes (57-XX)
1 Topological groups, Lie groups (22-XX)
1 Partial differential equations (35-XX)
1 Difference and functional equations (39-XX)
1 Sequences, series, summability (40-XX)
1 Global analysis, analysis on manifolds (58-XX)

Citations by Year

The data are displayed as stored in Wikidata under a Creative Commons CC0 License. Updates and corrections should be made in Wikidata.