Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

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

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 >>>

TR15-054 | 7th April 2015
Noga Alon, Noam Nisan, Ran Raz, Omri Weinstein

Welfare Maximization with Limited Interaction

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 >>>

TR06-076 | 4th May 2006
Noam Nisan

A Note on the computational hardness of evolutionary stable strategies

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 >>>

TR06-074 | 24th April 2006
Shahar Dobzinski, Noam Nisan

Approximations by Computationally-Efficient VCG-Based Mechanisms

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 >>>

TR97-008 | 16th March 1997
Noam Nisan, Ziv Bar-Yossef

Pointer Jumping Requires Concurrent Read

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 >>>

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

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.

more >>>

TR94-003 | 12th December 1994
Noam Nisan, Amnon Ta-Shma

Symmetric Logspace is Closed Under Complement

We present a Logspace, many-one reduction from the undirected
st-connectivity problem to its complement. This shows that

more >>>

TR94-001 | 12th December 1994
Noam Nisan, Avi Wigderson

On Rank vs. Communication Complexity

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.

more >>>

ISSN 1433-8092 | Imprint