All reports by Author Noam Nisan:

__
TR15-131
| 10th August 2015
__

Parikshit Gopalan, Noam Nisan, Rocco Servedio, Kunal Talwar, Avi Wigderson#### Smooth Boolean functions are easy: efficient algorithms for low-sensitivity functions

__
TR15-054
| 7th April 2015
__

Noga Alon, Noam Nisan, Ran Raz, Omri Weinstein#### Welfare Maximization with Limited Interaction

__
TR06-076
| 4th May 2006
__

Noam Nisan#### A Note on the computational hardness of evolutionary stable strategies

__
TR06-074
| 24th April 2006
__

Shahar Dobzinski, Noam Nisan#### Approximations by Computationally-Efficient VCG-Based Mechanisms

__
TR97-008
| 16th March 1997
__

Noam Nisan, Ziv Bar-Yossef#### Pointer Jumping Requires Concurrent Read

__
TR95-050
| 15th October 1995
__

Oded Goldreich, Noam Nisan, Avi Wigderson#### On Yao's XOR-Lemma

Revisions: 2
,
Comments: 1

__
TR95-029
| 15th June 1995
__

Oded Goldreich, Leonid Levin, Noam Nisan#### On Constructing 1-1 One-Way Functions

__
TR94-003
| 12th December 1994
__

Noam Nisan, Amnon Ta-Shma#### Symmetric Logspace is Closed Under Complement

__
TR94-001
| 12th December 1994
__

Noam Nisan, Avi Wigderson#### On Rank vs. Communication Complexity

Parikshit Gopalan, Noam Nisan, Rocco Servedio, Kunal Talwar, Avi Wigderson

A natural measure of smoothness of a Boolean function is its sensitivity (the largest number of Hamming neighbors of a point which differ from it in function value). The structure of smooth or equivalently low-sensitivity functions is still a mystery. A well-known conjecture states that every such Boolean function can ... more >>>

Noga Alon, Noam Nisan, Ran Raz, Omri Weinstein

We continue the study of welfare maximization in unit-demand (matching) markets, in a distributed information model

where agent's valuations are unknown to the central planner, and therefore communication is required to determine an

efficient allocation. Dobzinski, Nisan and Oren (STOC'14) showed that if the market size is $n$, ...
more >>>

Noam Nisan

We present a very simple reduction that when given a graph G and an integer k produces a game that has an evolutionary stable strategy if and only if the maximum clique size of G is not exactly k. Formally this shows that existence of evolutionary stable strategies is hard ... more >>>

Shahar Dobzinski, Noam Nisan

We consider computationally-efficient incentive-compatible

mechanisms that use the VCG payment scheme, and study how well they

can approximate the social welfare in auction settings. We obtain a

$2$-approximation for multi-unit auctions, and show that this is

best possible, even though from a purely computational perspective

an FPTAS exists. For combinatorial ...
more >>>

Noam Nisan, Ziv Bar-Yossef

We consider the well known problem of determining the k'th

vertex reached by chasing pointers in a directed graph of

out-degree 1. The famous "pointer doubling" technique

provides an O(log k) parallel time algorithm on a

Concurrent-Read Exclusive-Write (CREW) PRAM. We prove that ...
more >>>

Oded Goldreich, Noam Nisan, Avi Wigderson

Oded Goldreich, Leonid Levin, Noam Nisan

We show how to construct length-preserving 1-1 one-way

functions based on popular intractability assumptions (e.g., RSA, DLP).

Such 1-1 functions should not

be confused with (infinite) families of (finite) one-way permutations.

What we want and obtain is a single (infinite) 1-1 one-way function.

Noam Nisan, Amnon Ta-Shma

We present a Logspace, many-one reduction from the undirected

st-connectivity problem to its complement. This shows that

$SL=co-SL$

Noam Nisan, Avi Wigderson

This paper concerns the open problem of Lovasz and

Saks regarding the relationship between the communication complexity

of a boolean function and the rank of the associated matrix.

We first give an example exhibiting the largest gap known. We then

prove two related theorems.