Arrow Research search

Author name cluster

Noam Nisan

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

59 papers
2 author rows

Possible papers

59

NeurIPS Conference 2023 Conference Paper

Asynchronous Proportional Response Dynamics: Convergence in Markets with Adversarial Scheduling

  • Yoav Kolumbus
  • Menahem Levy
  • Noam Nisan

We study Proportional Response Dynamics (PRD) in linear Fisher markets, where participants act asynchronously. We model this scenario as a sequential process in which at each step, an adversary selects a subset of the players to update their bids, subject to liveness constraints. We show that if every bidder individually applies the PRD update rule whenever they are included in the group of bidders selected by the adversary, then, in the generic case, the entire dynamic converges to a competitive equilibrium of the market. Our proof technique reveals additional properties of linear Fisher markets, such as the uniqueness of the market equilibrium for generic parameters and the convergence of associated no swap regret dynamics and best response dynamics under certain conditions.

PDF Details

NeurIPS Conference 2022 Conference Paper

How and Why to Manipulate Your Own Agent: On the Incentives of Users of Learning Agents

  • Yoav Kolumbus
  • Noam Nisan

The usage of automated learning agents is becoming increasingly prevalent in many online economic applications such as online auctions and automated trading. Motivated by such applications, this paper is dedicated to fundamental modeling and analysis of the strategic situations that the users of automated learning agents are facing. We consider strategic settings where several users engage in a repeated online interaction, assisted by regret-minimizing learning agents that repeatedly play a "game" on their behalf. We propose to view the outcomes of the agents' dynamics as inducing a "meta-game" between the users. Our main focus is on whether users can benefit in this meta-game from "manipulating" their own agents by misreporting their parameters to them. We define a general framework to model and analyze these strategic interactions between users of learning agents for general games and analyze the equilibria induced between the users in three classes of games. We show that, generally, users have incentives to misreport their parameters to their own agents, and that such strategic user behavior can lead to very different outcomes than those anticipated by standard analysis.

PDF Details

NeurIPS Conference 2022 Conference Paper

The Query Complexity of Cake Cutting

  • Simina Branzei
  • Noam Nisan

We consider the query complexity of cake cutting in the standard query model and give lower and upper bounds for computing approximately envy-free, perfect, and equitable allocations with the minimum number of cuts. The lower bounds are tight for computing contiguous envy-free allocations among $n=3$ players and for computing perfect and equitable allocations with minimum number of cuts between $n=2$ players. For $\epsilon$-envy-free allocations with contiguous pieces, we also give an upper bound of $O(n/\epsilon)$ and lower bound of $\Omega(\log(1/\epsilon))$ queries for any number $n \geq 3$ of players. We also formalize moving knife procedures and show that a large subclass of this family, which captures all the known moving knife procedures, can be simulated efficiently with arbitrarily small error in the Robertson-Webb query model.

PDF Details

STOC Conference 2021 Conference Paper

Bipartite perfect matching as a real polynomial

  • Gal Beniamini
  • Noam Nisan

We obtain a description of the Bipartite Perfect Matching decision problem as a multilinear polynomial over the Reals. We show that it has full degree and (1− o n (1))· 2 n 2 monomials with non-zero coefficients. In contrast, we show that in the dual representation (switching the roles of 0 and 1) the number of monomials is only exponential in Θ( n log n ). Our proof relies heavily on the fact that the lattice of graphs which are “matching-covered” is Eulerian.

Details

SODA Conference 2021 Conference Paper

The Demand Query Model for Bipartite Matching

  • Noam Nisan

We introduce a “concrete complexity” model for studying algorithms for matching in bipartite graphs. The model is based on the “demand query” model used for combinatorial auctions. Most (but not all) known algorithms for bipartite matching seem to be translatable into this model including exact, approximate, sequential, parallel, and online ones. A perfect matching in a bipartite graph can be found in this model with O ( n 3/2 ) demand queries (in a bipartite graph with n vertices on each side) and our main open problem is to either improve the upper bound or prove a lower bound. An improved upper bound could yield “normal” algorithms whose running time is better than the fastest ones known, while a lower bound would rule out a faster algorithm for bipartite matching from within a large class of algorithms. Our main result is a lower bound for finding an approximately maximum size matching in parallel: A deterministic algorithm that runs in n o (1) rounds, where each round can make at most n 1. 99 demand queries cannot find a matching whose size is within n o (1) factor of the maximum. This is in contrast to randomized algorithms that can find a matching whose size is 99% of the maximum in O (log n ) rounds, each making n demand queries.

Details

AAAI Conference 2020 Conference Paper

Designing Committees for Mitigating Biases

  • Michal Feldman
  • Yishay Mansour
  • Noam Nisan
  • Sigal Oren
  • Moshe Tennenholtz

It is widely observed that individuals prefer to interact with others who are more similar to them (this phenomenon is termed homophily). This similarity manifests itself in various ways such as beliefs, values and education. Thus, it should not come as a surprise that when people make hiring choices, for example, their similarity to the candidate plays a role in their choice. In this paper, we suggest that putting the decision in the hands of a committee instead of a single person can reduce this bias. We study a novel model of voting in which a committee of experts is constructed to reduce the biases of its members. We first present voting rules that optimally reduce the biases of a given committee. Our main results include the design of committees, for several settings, that are able to reach a nearly optimal (unbiased) choice. We also provide a thorough analysis of the trade-offs between the committee size and the obtained error. Our model is inherently different from the well-studied models of voting that focus on aggregation of preferences or on aggregation of information due to the introduction of similarity biases.

PDF Details

STOC Conference 2019 Conference Paper

The communication complexity of local search

  • Yakov Babichenko
  • Shahar Dobzinski
  • Noam Nisan

We study a communication variant of local search. There is some fixed, commonly known graph G . Alice holds f A and Bob holds f B , both are functions that specify a value for each vertex. The goal is to find a local maximum of f A + f B with respect to G , i.e., a vertex v for which ( f A + f B )( v )≥ ( f A + f B )( u ) for each neighbor u of v .

Details

NeurIPS Conference 2018 Conference Paper

Universal Growth in Production Economies

  • Simina Branzei
  • Ruta Mehta
  • Noam Nisan

We study a simple variant of the von Neumann model of an expanding economy, in which multiple producers make goods according to their production function. The players trade their goods at the market and then use the bundles received as inputs for the production in the next round. The decision that players have to make is how to invest their money (i. e. bids) in each round. We show that a simple decentralized dynamic, where players update their bids on the goods in the market proportionally to how useful the investments were, leads to growth of the economy in the long term (whenever growth is possible) but also creates unbounded inequality, i. e. very rich and very poor players emerge. We analyze several other phenomena, such as how the relation of a player with others influences its development and the Gini index of the system.

PDF Details

STOC Conference 2017 Conference Paper

Efficient empirical revenue maximization in single-parameter auction environments

  • Yannai A. Gonczarowski
  • Noam Nisan

We present a polynomial-time algorithm that, given samples from the unknown valuation distribution of each bidder, learns an auction that approximately maximizes the auctioneer's revenue in a variety of single-parameter auction environments including matroid environments, position environments, and the public project environment. The valuation distributions may be arbitrary bounded distributions (in particular, they may be irregular, and may differ for the various bidders), thus resolving a problem left open by previous papers. The analysis uses basic tools, is performed in its entirety in value-space, and simplifies the analysis of previously known results for special cases. Furthermore, the analysis extends to certain single-parameter auction environments where precise revenue maximization is known to be intractable, such as knapsack environments.

Details

STOC Conference 2017 Conference Paper

The menu-size complexity of revenue approximation

  • Moshe Babaioff
  • Yannai A. Gonczarowski
  • Noam Nisan

We consider a monopolist that is selling n items to a single additive buyer, where the buyer's values for the items are drawn according to independent distributions F 1 , F 2 ,…, F n that possibly have unbounded support. It is well known that - unlike in the single item case - the revenue-optimal auction (a pricing scheme) may be complex, sometimes requiring a continuum of menu entries. It is also known that simple auctions with a finite bounded number of menu entries can extract a constant fraction of the optimal revenue. Nonetheless, the question of the possibility of extracting an arbitrarily high fraction of the optimal revenue via a finite menu size remained open. In this paper, we give an affirmative answer to this open question, showing that for every n and for every ε>0, there exists a complexity bound C = C ( n ,ε) such that auctions of menu size at most C suffice for obtaining a (1-ε) fraction of the optimal revenue from any F 1 ,…, F n . We prove upper and lower bounds on the revenue approximation complexity C ( n ,ε), as well as on the deterministic communication complexity required to run an auction that achieves such an approximation.

Details

FOCS Conference 2016 Conference Paper

Knuth Prize Lecture: Complexity of Communication in Markets

  • Noam Nisan

Summary form only given. The complete presentation was not made available for publication as part of the conference proceedings. A classical point of view in Economic Theory is that prices in markets serve as a communication mechanism between the participants (buyers and sellers) in the market. I will analyze the communication complexity (in the standard sense used in Theoretical Computer Science) required for obtaining efficiency and equilibrium in several scenarios of markets of indivisible goods.

Details

FOCS Conference 2015 Conference Paper

Welfare Maximization with Limited Interaction

  • 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, then r rounds of interaction (with logarithmic bandwidth) suffice to obtain an n 1/(r+1) -approximation to the optimal social welfare. In particular, this implies that such markets converge to a stable state (constant approximation) in time logarithmic in the market size. We obtain the first multi-round lower bound for this setup. We show that even if the allowable per-round bandwidth of each agent is n ε(r), the approximation ratio of any r-round (randomized) protocol is no better than Ω(n 1/5r+1), implying an Ω(log log n) lower bound on the rate of convergence of the market to equilibrium. Our construction and technique may be of interest to round-communication tradeoffs in the more general setting of combinatorial auctions, for which the only known lower bound is for simultaneous (r = 1) protocols [DNO14].

Details

AAMAS Conference 2012 Conference Paper

Fair Allocation Without Trade

  • Avital Gutman
  • Noam Nisan

We consider the age-old problem of allocating items among different agents in a way that is efficient and fair. Two papers, by Dolev et al. and Ghodsi et al. , have recently studied this problem in the context of computer systems. Both papers had similar models for agent preferences, but advocated different notions of fairness. We formalize both fairness notions in economic terms, extending them to apply to a larger family of utilities. Noting that in settings with such utilities efficiency is easily achieved in multiple ways, we study notions of fairness as criteria for choosing between different efficient allocations. Our technical results are algorithms for finding fair allocations corresponding to two fairness notions: Regarding the notion suggested by Ghodsi et al. , we present a polynomialtime algorithm that computes an allocation for a general class of fairness notions, in which their notion is included. For the other, suggested by Dolev et al. , we show that a competitive market equilibrium achieves the desired notion of fairness, thereby obtaining a polynomial-time algorithm that computes such a fair allocation and solving the main open problem raised by Dolev et al.

PDF

SODA Conference 2012 Conference Paper

Sketching valuation functions

  • Ashwinkumar Badanidiyuru
  • Shahar Dobzinski
  • Hu Fu 0001
  • Robert Kleinberg
  • Noam Nisan
  • Tim Roughgarden

Motivated by the problem of querying and communicating bidders' valuations in combinatorial auctions, we study how well different classes of set functions can be sketched. More formally let f be a function mapping subsets of some ground set [ n ] to the non-negative real numbers. We say that f′ is an α-sketch of f if for every set S, the value f′ ( S ) lies between f ( S )/α and f ( S ), and f′ can be specified by poly( n ) bits. We show that for every subadditive function f there exists an α-sketch where α = n 1/2 · O (polylog( n )). Furthermore, we provide an algorithm that finds these sketches with a polynomial number of demand queries. This is essentially the best we can hope for since: 1. We show that there exist subadditive functions (in fact, XOS functions) that do not admit an o ( n 1/2 ) sketch. (Balcan and Harvey [3] previously showed that there exist functions belonging to the class of substitutes valuations that do not admit an O ( n 1/3 ) sketch.) 2. We prove that every deterministic algorithm that accesses the function via value queries only cannot guarantee a sketching ratio better than n 1−ε. We also show that coverage functions, an interesting subclass of submodular functions, admit arbitrarily good sketches. Finally, we show an interesting connection between sketching and learning. We show that for every class of valuations, if the class admits an α-sketch, then it can be α-approximately learned in the PMAC model of Balcan and Harvey. The bounds we prove are only information-theoretic and do not imply the existence of computationally efficient learning algorithms in general.

Details

FOCS Conference 2008 Conference Paper

Elections Can be Manipulated Often

  • Ehud Friedgut
  • Gil Kalai
  • Noam Nisan

The Gibbard-Satterthwaite theorem states that every non-trivial voting method among at least 3 alternatives can be strategically manipulated. We prove a quantitative version of the Gibbard-Satterthwaite theorem: a random manipulation by a single random voter will succeed with non-negligible probability for every neutral voting method among 3 alternatives that is far from being a dictatorship.

Details

FOCS Conference 2008 Conference Paper

Multi-unit Auctions with Budget Limits

  • Shahar Dobzinski
  • Ron Lavi
  • Noam Nisan

We study multi-unit auctions where the bidders have a budget constraint, a situation very common in practice that has received very little attention in the auction theory literature. Our main result is an impossibility: there are no incentive-compatible auctions that always produce a Pareto-optimal allocation. We also obtain some surprising positive results for certain special cases.

Details

STOC Conference 2007 Conference Paper

Limitations of VCG-based mechanisms

  • Shahar Dobzinski
  • Noam Nisan

We consider computationally-efficient incentive-compatiblemechanisms that use the VCG payment scheme, and study how well theycan approximate the social welfare in auction settings. We present anovel technique for setting lower bounds on the approximation ratioof this type of mechanisms. Specifically, for combinatorial auctionsamong submodular (and thus also subadditive) bidders we prove an Ω(m 1/6 ) lower bound, which is close to the knownupper bound of O(m 1/2 ), and qualitatively higher than theconstant factor approximation possible from a purely computationalpoint of view.

Details

STOC Conference 2006 Conference Paper

Truthful randomized mechanisms for combinatorial auctions

  • Shahar Dobzinski
  • Noam Nisan
  • Michael Schapira

We design two computationally-efficient incentive-compatible mechanisms for combinatorial auctions with general bidder preferences. Both mechanisms are randomized, and are incentive-compatible in the universal sense. This is in contrast to recent previous work that only addresses the weaker notion of incentive compatibility in expectation. The first mechanism obtains an O(√m)-approximation of the optimal social welfare for arbitrary bidder valuations -- this is the best approximation possible in polynomial time. The second one obtains an O(log 2 m)-approximation for a subclass of bidder valuations that includes all submodular bidders. This improves over the best previously obtained incentive-compatible mechanism for this class which only provides an O(√ m)-approximation.

Details

STOC Conference 2005 Conference Paper

Approximation algorithms for combinatorial auctions with complement-free bidders

  • Shahar Dobzinski
  • Noam Nisan
  • Michael Schapira

We exhibit three approximation algorithms for the allocation problem in combinatorial auctions with complement free bidders. The running time of these algorithms is polynomial in the number of items $m$ and in the number of bidders n, even though the "input size" is exponential in m. The first algorithm provides an O(log m) approximation. The second algorithm provides an O(√ m) approximation in the weaker model of value oracles. This algorithm is also incentive compatible. The third algorithm provides an improved 2-approximation for the more restricted case of " XOS bidders", a class which strictly contains submodular bidders. We also prove lower bounds on the possible approximations achievable for these classes of bidders. These bounds are not tight and we leave the gaps as open problems.

Details

TARK Conference 2005 Conference Paper

Exponential communication inefficiency of demand queries

  • Noam Nisan
  • Ilya Segal

In the problem of …nding an e¢ cient allocation when agents’utilities are privately known, we examine the e¤ect of restricting attention to mechanisms using “demand queries, ” which ask agents to report an optimal allocation given a price list. We construct a combinatorial allocation problem with m items and two agents whose valuations lie in a certain class, such that (i) e¢ ciency can be obtained with a mechanism using O (m) bits, but (ii) any demand-query mechanism guaranteeing a higher e¢ ciency than giving all items to one agent uses a number of queries that is exponential in m. The same is proven for any demand-query mechanism achieving an improvement in expected e¢ ciency, for a constructed joint probability distribution over agents’valuations from the class. These results cast doubt on the usefulness of such common combinatorial allocation mechanisms as “iterative auctions”and other “preference elicitation” mechanisms using demand queries, as well as “value queries” and “order queries” (which are easily replicated with demand queries in our setting).

Details

TCS Journal 2004 Journal Article

Competitive analysis of incentive compatible on-line auctions

  • Ron Lavi
  • Noam Nisan

This paper studies auctions in a setting where the different bidders arrive at different times and the auction mechanism is required to make decisions about each bid as it is received. Such settings occur in computerized auctions of computational resources as well as in other settings. We call such auctions, on-line auctions. We first characterize exactly on-line auctions that are incentive compatible, i. e. where rational bidders are always motivated to bid their true valuation. We then embark on a competitive worst-case analysis of incentive compatible on-line auctions. We obtain several results, the cleanest of which is an incentive compatible on-line auction for a large number of identical items. This auction has an optimal competitive ratio, both in terms of seller's revenue and in terms of the total social efficiency obtained.

Details DOI

TARK Conference 2003 Conference Paper

Incentive compatible multi unit combinatorial auctions

  • Yair Bartal
  • Rica Gonen
  • Noam Nisan

This paper deals with multi-unit combinatorial auctions where there are n types of goods for sale, and for each good there is some fixed number of units. We focus on the case where each bidder desires a relatively small number of units of each good. In particular, this includes the case where each good has exactly k units, and each bidder desires no more than a single unit of each good. We provide incentive compatible mechanisms for combinatorial auctions for the general case where bidders are not limited to singleminded valuations. The mechanisms we give have approximation ratios close to the best possible for both on-line and off-line scenarios. This is the first result where non-VCG mechanisms are derived for non-single minded bidders for a natural model of combinatorial auctions.

Details

FOCS Conference 2003 Conference Paper

Towards a Characterization of Truthful Combinatorial Auctions

  • Ron Lavi
  • Ahuva Mu'alem
  • Noam Nisan

This paper analyzes incentive compatible (truthful) mechanisms over restricted domains of preferences, the leading example being combinatorial auctions. Our work generalizes the characterization of Roberts (1979) who showed that truthful mechanisms over unrestricted domains with at least 3 possible outcomes must be "affine maximizers". We show that truthful mechanisms for combinatorial auctions (and related restricted domains) must be "almost affine maximizers" if they also satisfy an additional requirement of "independence of irrelevant alternatives". This requirement is without loss of generality for unrestricted domains as well as for auctions between two players where all goods must be allocated. This implies unconditional results for these cases, including a new proof of Roberts' theorem. The computational implications of this characterization are severe, as reasonable "almost affine maximizers" are shown to be as computationally hard as exact optimization. This implies the near-helplessness of such truthful polynomial-time auctions in all cases where exact optimization is computationally intractable.

Details

FOCS Conference 2002 Conference Paper

Auctions with Severely Bounded Communication

  • Liad Blumrosen
  • Noam Nisan

We study auctions with severe bounds on the communication allowed: each bidder may only transmit t bits of information to the auctioneer. We consider both welfare-maximizing and revenue-maximizing auctions under this communication restriction. For both measures, we determine the optimal auction and show that the loss incurred relative to unconstrained auctions is mild. We prove unsurprising properties of these kinds of auctions, e. g. that discrete prices are informationally efficient, as well as some surprising properties, e. g. that asymmetric auctions are better than symmetric ones.

Details

FOCS Conference 1995 Conference Paper

Lower Bounds for Arithmetic Circuits via Partial Serivatives (Preliminary Version)

  • Noam Nisan
  • Avi Wigderson

We describe a new technique for obtaining lower bounds on restricted classes of non-monotone arithmetic circuits. The heart of this technique is a complexity measure for multivariate polynomials, based on the linear span of their partial derivatives. We use the technique to obtain new lower bounds for computing symmetric polynomials and iterated matrix products.

Details

FOCS Conference 1994 Conference Paper

On Rank vs. Communication Complexity

  • Noam Nisan
  • Avi Wigderson

This paper concerns the open problem of Lovasz and Saks (1988) 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. >

Details

FOCS Conference 1994 Conference Paper

Products and Help Bits in Decision Trees

  • Noam Nisan
  • Steven Rudich
  • Michael E. Saks

We investigate two problems concerning the complexity of evaluating a function f at k-tuple of unrelated inputs by k parallel decision tree algorithms. In the product problem, for some fixed depth bound d, we seek to maximize the fraction of input k-tuples for which all k decision trees are correct. Assume that for a single input to f, the best decision tree algorithm of depth d is correct on a fraction p of inputs. We prove that the maximum fraction of k-tuples on which k depth d algorithms are all correct is at most p/sup k/, which is the trivial lower bound. We show that if we replace the depth d restriction by "expected depth d", then this result fails. In the help-bit problem, we are permitted to ask k-1 arbitrary binary questions about the k-tuple of inputs. For each possible k-1-tuple of answers to these queries we will have a k-tuple of decision trees which are supposed to correctly compute all functions on k-tuples that are consistent with the particular answers. The complexity here is the maximum depth of any of the trees in the algorithm. We show that for all k sufficiently large, this complexity is equal to deg/sup s/(f) which is the minimum degree of a multivariate polynomial whose sign is equal to f. Finally, we give a brief discussion of these problems in the context of other complexity models. >

Details

TCS Journal 1993 Journal Article

On read once vs. multiple access to randomness in logspace

  • Noam Nisan

In the “correct” definition of randomized space-bounded computation, the machine has access to a random coin. The coin can be flipped at will, but outcomes of previous coin flips cannot be recalled unless they are saved in the machine's limited memory. In contrast to this read-once mechanism of accessing the random source, one may consider Turing machines which have access to a random tape. Here, the random bits may be multiply accessed by the machine. In this note we show a very concrete sense in which multiple access to the random bits is better than read-once access to them: Every language accepted with bounded 2-sided error by a read-once-randomized logspace machine, can be accepted with zero error by a randomized logspace machine having multiple access to the random bits. Finally, we characterize the clsss of languates that can be accepted with two-sided error by randomized logspace machines with multiple access to the random bits as exactly the class of languages that are in logspace to almost every oracle.

Details DOI

TCS Journal 1993 Journal Article

The computational complexity of universal hashing

  • Yishay Mansour
  • Noam Nisan
  • Prasoon Tiwari

Any implementation of Carter-Wegman universal hashing from n-bit strings to m-bit strings requires a time-space tradeoff of TS=Ω(nm). The bound holds in the general boolean branching program model and, thus, in essentially any model of computation. As a corollary, computing a + b ∗ c in any field F requires a quadratic time-space tradeoff, and the bound holds for any representation of the elements of the field. Other lower bounds on the complexity of any implementation of universal hashing are given as well: quadratic AT 2 bound for VLSI implementation; Ω(logn) parallel time bound on a CREW PRAM; and exponential size for constant-depth circuits.

Details DOI

STOC Conference 1992 Conference Paper

Approximations of General Independent Distributions

  • Guy Even
  • Oded Goldreich 0001
  • Michael Luby
  • Noam Nisan
  • Boban Velickovic

We describe efficient constructions of small probability spaces that approximate the independent distribution for general random variables. Previous work on efficient constructions concentrate on approximations of the independent distribution for the special case of uniform boolean-valued random variables. Our results yield efficient constructions of small sets with low discrepancy in high dimensional space and have applications to derandomizing randomized algorithms.

Details

STOC Conference 1992 Conference Paper

On the Degree of Boolean Functions as Real Polynomials

  • Noam Nisan
  • Mario Szegedy

Every boolean function may be represented as a real polynomial. In this paper we characterize the degree of this polynomial in terms of certain combinatorial properties of the boolean function. Our first result is a tight lower bound of Ω(log n ) on the degree needed to represent any boolean function that depends on n variables. Our second result states that for every boolean function f the following measures are all polynomially related:(1) The decision tree complexity of f . (2) The degree of the polynomial representing f . (3) The smallest degree of a polynomial approximating f in the L max norm.

Details

FOCS Conference 1992 Conference Paper

Undirected Connectivity in O(log ^1. 5 n) Space

  • Noam Nisan
  • Endre Szemerédi
  • Avi Wigderson

The authors present a deterministic algorithm for the connectivity problem on undirected graphs that runs in O(log/sup 1. 5/n) space. Thus, the recursive doubling technique of Savich (1970) which requires Theta (log/sup 2/n) space is not optimal for this problem. >

Details

FOCS Conference 1990 Conference Paper

Algebraic Methods for Interactive Proof Systems

  • Carsten Lund
  • Lance Fortnow
  • Howard J. Karloff
  • Noam Nisan

An algebraic technique for the construction of interactive proof systems is proposed. The technique is used to prove that every language in the polynomial-time hierarchy has an interactive proof system. For the proof, a method is developed for reducing the problem of verifying the value of a low-degree polynomial at two points to verifying the value at one new point. The results have implications for program checking, verification, and self-correction. >

Details

FOCS Conference 1989 Conference Paper

Constant Depth Circuits, Fourier Transform, and Learnability

  • Nati Linial
  • Yishay Mansour
  • Noam Nisan

Boolean functions in AC/sup O/ are studied using the harmonic analysis of the cube. The main result is that an AC/sup O/ Boolean function has almost all of its power spectrum on the low-order coefficients. This result implies the following properties of functions in AC/sup O/: functions in AC/sup O/ have low average sensitivity; they can be approximated well be a real polynomial of low degree; they cannot be pseudorandom function generators and their correlation with any polylog-wide independent probability distribution is small. An O(n/sup polylog(/ /sup sup)/ /sup (n)/)-time algorithm for learning functions in AC/sup O/ is obtained. The algorithm observed the behavior of an AC/sup O/ function on O(n/sup polylog/ /sup (n)/) randomly chosen inputs and derives a good approximation for the Fourier transform of the function. This allows it to predict with high probability the value of the function on other randomly chosen inputs. >

Details

STOC Conference 1989 Conference Paper

CREW PRAMs and Decision Trees

  • Noam Nisan

This paper gives a full characterization of the time needed to compute a Boolean function on a CREW PRAM with an unlimited number of processors.

Details

FOCS Conference 1988 Conference Paper

Hardness vs. Randomness (Extended Abstract)

  • Noam Nisan
  • Avi Wigderson

A simple construction for a pseudorandom bit generator is presented. It stretches a short string of truly random bits into a long string that looks random to any algorithm from a complexity class C (e. g. P, NC, PSPACE, etc.), using an arbitrary function that is hard for C. This generator reveals an equivalence between the problems of proving lower bounds and the problem of generating good pseudorandom sequences. Combining this construction with other arguments, a number of consequences are obtained. >

Details
v2026.09.13