×

zbMATH — the first resource for mathematics

Nisan, Noam

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
Documents Indexed: 106 Publications since 1989, including 2 Books
all top 5

Co-Authors

9 single-authored
14 Dobzinski, Shahar
13 Wigderson, Avi
9 Babaioff, Moshe
7 Blumrosen, Liad
6 Lavi, Ron
5 Linial, Nathan
4 Gonczarowski, Yannai A.
4 Impagliazzo, Russell
4 Mansour, Yishay
4 Schapira, Michael
3 Feldman, Michal
3 Goldreich, Oded
3 Hart, Sergiu
3 Kremer, Ilan
3 Kushilevitz, Eyal
3 Mu’alem, Ahuva
3 Naor, Moni
3 Parnas, Michal
3 Ron, Dana
3 Ronen, Amir
3 Rudich, Steven
3 Segal, Ilya R.
3 Ta-Shma, Amnon
2 Babai, László
2 Bro Miltersen, Peter
2 Dolev, Danny
2 Feldman, David Victor
2 Fortnow, Lance J.
2 Harari, Yuval
2 Luby, Michael G.
2 Oren, Sigal
2 Ostrovsky, Rafail
2 Rosenbaum, Will
2 Roughgarden, Tim
2 Safra, Shmuel
2 Saks, Michael E.
2 Shamir, Adi
2 Szegedy, Mario
2 Vishkin, Uzi
2 Zuckerman, David
1 Abraham, Ittai
1 Aharonov, Dorit
1 Babichenko, Yakov
1 Badanidiyuru, Ashwinkumar
1 Bar-Yossef, Ziv
1 Bikhchandani, Sushil
1 Chatterji, Shurojit
1 Dughmi, Shaddin
1 Even, Guy
1 Feder, Tomás
1 Friedgut, Ehud
1 Fu, Hu
1 Gavoille, Cyril
1 Gopalan, Parikshit
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 Keller, Nathan
1 Kitaev, Alexei Yu.
1 Kleinberg, Robert D.
1 Lehmann, Benny
1 Levin, Leonid A.
1 Lucier, Brendan
1 Lund, Carsten
1 Malkhi, Dahlia
1 Motwani, Rajeev
1 Pavlov, Elan
1 Sen, Arunava
1 Servedio, Rocco A.
1 Soroker, Danny
1 Szemerédi, Endre
1 Talgam-Cohen, Inbal
1 Talwar, Kunal
1 Tardos, Éva
1 Thorup, Mikkel
1 Tiwari, Prasoon
1 Vazirani, Vijay V.
1 Velickovic, Boban
1 Winter, Eyal

Publications by Year

Citations contained in zbMATH Open

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

Cited by 2,267 Authors

29 Nisan, Noam
18 Fortnow, Lance J.
16 Bollig, Beate
16 Goldreich, Oded
15 Wigderson, Avi
13 Allender, Eric W.
13 Feldman, Michal
13 Koutsoupias, Elias
13 Servedio, Rocco A.
13 Shaltiel, Ronen
12 Penna, Paolo
12 Pitassi, Toniann
12 Zuckerman, David
11 Ambainis, Andris
11 Braverman, Mark
11 Viola, Emanuele
11 Yehudayoff, Amir
10 Buhrman, Harry
10 Dobzinski, Shahar
10 Hromkovič, Juraj
10 Lavi, Ron
10 Saks, Michael E.
10 van Melkebeek, Dieter
9 Caragiannis, Ioannis
9 de Wolf, Ronald Michiel
9 Feige, Uriel
9 Göös, Mika
9 Markakis, Evangelos
9 Meir, Or
9 Müller, Rudolf
9 Raz, Ran
9 Roughgarden, Tim
9 Sergioli, Giuseppe
9 Ventre, Carmine
8 Arvind, Vikraman
8 Chattopadhyay, Arkadev
8 Feigenbaum, Joan
8 Filmus, Yuval
8 Giuntini, Roberto
8 Jain, Rahul
8 Kleinberg, Robert D.
8 Lee, Troy
8 Mossel, Elchanan
8 Schnitger, Georg
8 Shioura, Akiyoshi
8 Shpilka, Amir
8 Shraibman, Adi
8 Srinivasan, Srikanth
8 Tal, Avishay
8 Vinodchandran, N. Variyam
7 Applebaum, Benny
7 Giannakopoulos, Yiannis
7 Impagliazzo, Russell
7 Kabanets, Valentine
7 Kayal, Neeraj
7 Köbler, Johannes
7 Lovett, Shachar
7 Mishra, Debasis
7 Papadimitriou, Christos Harilaos
7 Parkes, David C.
7 Procaccia, Ariel D.
7 Sauerhoff, Martin
7 Serna, Maria José
7 Sherstov, Alexander A.
7 Srinivasan, Aravind
7 Sun, Xiaoming
7 Ta-Shma, Amnon
7 Vadhan, Salil P.
7 Wegener, Ingo
7 Williams, Richard Ryan
7 Woodruff, David P.
7 Zhang, Shengyu
6 Amano, Kazuyuki
6 Anshelevich, Elliot
6 Auletta, Vincenzo
6 Ben-Sasson, Eli
6 Blum, Avrim L.
6 Blumrosen, Liad
6 Christodoulou, George C.
6 Fraigniaud, Pierre
6 Freytes, Hector
6 Gonen, Rica
6 Gravin, Nick
6 Hitchcock, John M.
6 Koucký, Michal
6 Ledda, Antonio
6 Limaye, Nutan
6 Linial, Nathan
6 Lu, Chijen
6 Mansour, Yishay
6 Narahari, Yadati
6 Nishimura, Harumichi
6 O’Donnell, Ryan
6 Peleg, David
6 Pudlák, Pavel
6 Rapaport, Ivan
6 Reingold, Omer
6 Reyzin, Leonid
6 Saha, Chandan
6 Saptharishi, Ramprasad
...and 2,167 more Authors
all top 5

Cited in 205 Serials

170 Theoretical Computer Science
109 Journal of Computer and System Sciences
86 SIAM Journal on Computing
81 Computational Complexity
65 Theory of Computing Systems
64 Algorithmica
62 Games and Economic Behavior
58 Information Processing Letters
39 Information and Computation
27 Journal of Economic Theory
23 Discrete Applied Mathematics
23 Journal of Cryptology
23 Distributed Computing
21 Combinatorica
20 Mathematical Programming. Series A. Series B
18 Artificial Intelligence
15 Random Structures & Algorithms
15 European Journal of Operational Research
12 Mathematics of Operations Research
11 Journal of the ACM
10 Journal of Mathematical Economics
10 Combinatorics, Probability and Computing
9 International Journal of Foundations of Computer Science
8 SIAM Journal on Discrete Mathematics
8 Economic Theory
8 RAIRO. Theoretical Informatics and Applications
8 Natural Computing
7 Operations Research
7 Operations Research Letters
7 Annals of Mathematics and Artificial Intelligence
6 Discrete Mathematics
6 Mathematical Social Sciences
6 Annals of Pure and Applied Logic
6 Social Choice and Welfare
6 Linear Algebra and its Applications
6 Journal of Combinatorial Optimization
5 Annals of Operations Research
5 Economics Letters
5 Annals of Mathematics. Second Series
5 CEJOR. Central European Journal of Operations Research
5 OR Spectrum
5 Quantum Information Processing
4 Communications in Mathematical Physics
4 International Journal of Theoretical Physics
4 Automatica
4 Information Sciences
4 International Journal of Game Theory
4 The Journal of Symbolic Logic
4 Computers & Operations Research
4 Journal of Theoretical Probability
4 Journal of Global Optimization
4 Bulletin of the American Mathematical Society. New Series
4 Journal of Mathematical Sciences (New York)
4 Constraints
4 Journal of High Energy Physics
4 International Game Theory Review
4 Games
4 ACM Transactions on Computation Theory
3 Israel Journal of Mathematics
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 Machine Learning
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 Mathematical Problems in Engineering
3 Chicago Journal of Theoretical Computer Science
3 Journal of Scheduling
3 New Journal of Physics
3 Review of Economic Design
3 Sādhanā
3 Discrete Optimization
2 Acta Informatica
2 International Journal of General Systems
2 Journal of Mathematical Physics
2 Journal of Statistical Physics
2 Acta Mathematica
2 Journal of Number Theory
2 Mathematical Systems Theory
2 Transactions of the American Mathematical Society
2 Statistics & Probability Letters
2 SIAM Journal on Algebraic and Discrete Methods
2 Journal of Complexity
2 Journal of Computer Science and Technology
2 Journal of Parallel and Distributed Computing
2 Automation and Remote Control
2 SIAM Journal on Optimization
2 Mathematical Logic Quarterly (MLQ)
2 Electronic Journal of Probability
2 Sbornik: Mathematics
2 Soft Computing
2 Mathematical Methods of Operations Research
2 Data Mining and Knowledge Discovery
2 Journal of Mathematical Logic
...and 105 more Serials
all top 5

Cited in 41 Fields

1,075 Computer science (68-XX)
485 Game theory, economics, finance, and other social and behavioral sciences (91-XX)
240 Information and communication theory, circuits (94-XX)
206 Operations research, mathematical programming (90-XX)
163 Combinatorics (05-XX)
100 Quantum theory (81-XX)
62 Mathematical logic and foundations (03-XX)
50 Probability theory and stochastic processes (60-XX)
42 Order, lattices, ordered algebraic structures (06-XX)
32 Numerical analysis (65-XX)
28 Number theory (11-XX)
26 Linear and multilinear algebra; matrix theory (15-XX)
20 Statistics (62-XX)
11 Convex and discrete geometry (52-XX)
11 Biology and other natural sciences (92-XX)
10 Functional analysis (46-XX)
8 Field theory and polynomials (12-XX)
8 Operator theory (47-XX)
8 Systems theory; control (93-XX)
7 Commutative algebra (13-XX)
7 Group theory and generalizations (20-XX)
7 Harmonic analysis on Euclidean spaces (42-XX)
6 Algebraic geometry (14-XX)
6 Statistical mechanics, structure of matter (82-XX)
5 Measure and integration (28-XX)
5 Calculus of variations and optimal control; optimization (49-XX)
4 General and overarching topics; collections (00-XX)
4 Dynamical systems and ergodic theory (37-XX)
4 Approximations and expansions (41-XX)
4 Relativity and gravitational theory (83-XX)
3 Functions of a complex variable (30-XX)
2 Real functions (26-XX)
2 Geometry (51-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 Abstract harmonic analysis (43-XX)
1 Global analysis, analysis on manifolds (58-XX)

Citations by Year

Wikidata Timeline

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