All reports by Author Chris Umans:

__
TR11-067
| 25th April 2011
__

Noga Alon, Amir Shpilka, Chris Umans#### On Sunflowers and Matrix Multiplication

Comments: 1

__
TR10-186
| 2nd December 2010
__

Bill Fefferman, Ronen Shaltiel, Chris Umans, Emanuele Viola#### On beating the hybrid argument

__
TR09-145
| 20th December 2009
__

Shankar Kalyanaraman, Chris Umans#### The Complexity of Rationalizing Network Formation

__
TR09-107
| 28th October 2009
__

Kevin Dick, Chris Umans#### Improved inapproximability factors for some $\Sigma_2^p$ minimization problems

__
TR09-068
| 1st September 2009
__

Dave Buchfuhrer, Chris Umans#### Limits on the Social Welfare of Maximal-In-Range Auction Mechanisms

__
TR08-021
| 3rd March 2008
__

Shankar Kalyanaraman, Chris Umans#### The Complexity of Rationalizing Matchings

__
TR07-069
| 29th July 2007
__

Ronen Shaltiel, Chris Umans#### Low-end uniform hardness vs. randomness tradeoffs for AM

__
TR07-059
| 6th July 2007
__

Shankar Kalyanaraman, Chris Umans#### Algorithms for Playing Games with Limited Randomness

__
TR06-134
| 18th October 2006
__

Venkatesan Guruswami, Chris Umans, Salil Vadhan#### Extractors and condensers from univariate polynomials

Revisions: 1

__
TR06-128
| 5th October 2006
__

Shankar Kalyanaraman, Chris Umans#### On obtaining pseudorandomness from error-correcting codes.

__
TR04-086
| 12th October 2004
__

Ronen Shaltiel, Chris Umans#### Pseudorandomness for Approximate Counting and Sampling

__
TR04-001
| 11th December 2003
__

Lance Fortnow, Russell Impagliazzo, Chris Umans#### On the complexity of succinct zero-sum games

Noga Alon, Amir Shpilka, Chris Umans

We present several variants of the sunflower conjecture of Erd\H{o}s and Rado and discuss the relations among them.

We then show that two of these conjectures (if true) imply negative answers to questions of Coppersmith and Winograd and Cohn et al. regarding possible approaches for obtaining fast matrix multiplication algorithms. ... more >>>

Bill Fefferman, Ronen Shaltiel, Chris Umans, Emanuele Viola

The {\em hybrid argument}

allows one to relate

the {\em distinguishability} of a distribution (from

uniform) to the {\em

predictability} of individual bits given a prefix. The

argument incurs a loss of a factor $k$ equal to the

bit-length of the

distributions: $\epsilon$-distinguishability implies only

$\epsilon/k$-predictability. ...
more >>>

Shankar Kalyanaraman, Chris Umans

We study the complexity of {\em rationalizing} network formation. In

this problem we fix an underlying model describing how selfish

parties (the vertices) produce a graph by making individual

decisions to form or not form incident edges. The model is equipped

with a notion of stability (or equilibrium), and we ...
more >>>

Kevin Dick, Chris Umans

We give improved inapproximability results for some minimization problems in the second level of the Polynomial-Time Hierarchy. Extending previous work by Umans [Uma99], we show that several variants of DNF minimization are $\Sigma_2^p$-hard to approximate to within factors of $n^{1/3-\epsilon}$ and $n^{1/2-\epsilon}$ (where the previous results achieved $n^{1/4 - \epsilon}$), ... more >>>

Dave Buchfuhrer, Chris Umans

Many commonly-used auction mechanisms are ``maximal-in-range''. We show that any maximal-in-range mechanism for $n$ bidders and $m$ items cannot both approximate the social welfare with a ratio better than $\min(n, m^\eta)$ for any constant $\eta < 1/2$ and run in polynomial time, unless $NP \subseteq P/poly$. This significantly improves upon ... more >>>

Shankar Kalyanaraman, Chris Umans

Given a set of observed economic choices, can one infer

preferences and/or utility functions for the players that are

consistent with the data? Questions of this type are called {\em

rationalization} or {\em revealed preference} problems in the

economic literature, and are the subject of a rich body of work.

Ronen Shaltiel, Chris Umans

In 1998, Impagliazzo and Wigderson proved a hardness vs. randomness tradeoff for BPP in the {\em uniform setting}, which was subsequently extended to give optimal tradeoffs for the full range of possible hardness assumptions by Trevisan and Vadhan (in a slightly weaker setting). In 2003, Gutfreund, Shaltiel and Ta-Shma proved ... more >>>

Shankar Kalyanaraman, Chris Umans

We study multiplayer games in which the participants have access to

only limited randomness. This constrains both the algorithms used to

compute equilibria (they should use little or no randomness) as well

as the mixed strategies that the participants are capable of playing

(these should be sparse). We frame algorithmic ...
more >>>

Venkatesan Guruswami, Chris Umans, Salil Vadhan

We give new constructions of randomness extractors and lossless condensers that are optimal to within constant factors in both the seed length and the output length. For extractors, this matches the parameters of the current best known construction [LRVW03]; for lossless condensers, the previous best constructions achieved optimality to within ... more >>>

Shankar Kalyanaraman, Chris Umans

A number of recent results have constructed randomness extractors

and pseudorandom generators (PRGs) directly from certain

error-correcting codes. The underlying construction in these

results amounts to picking a random index into the codeword and

outputting $m$ consecutive symbols (the codeword is obtained from

the weak random source in the case ...
more >>>

Ronen Shaltiel, Chris Umans

We study computational procedures that use both randomness and nondeterminism. Examples are Arthur-Merlin games and approximate counting and sampling of NP-witnesses. The goal of this paper is to derandomize such procedures under the weakest possible assumptions.

Our main technical contribution allows one to ``boost'' a given hardness assumption. One special ... more >>>

Lance Fortnow, Russell Impagliazzo, Chris Umans

We study the complexity of solving succinct zero-sum games,

i.e., the

games whose payoff matrix $M$ is given implicitly by a Boolean circuit

$C$ such that $M(i,j)=C(i,j)$. We complement the known $\EXP$-hardness

of computing the \emph{exact} value of a succinct zero-sum game by

several results on \emph{approximating} the value. (1) ...
more >>>