Next

__
TR23-040
| 28th March 2023
__

Edward Pyne, Ran Raz, Wei Zhan#### Certified Hardness vs. Randomness for Log-Space

__
TR23-039
| 28th March 2023
__

Arkadev Chattopadhyay, Yogesh Dahiya, Meena Mahajan#### Query Complexity of Search Problems

__
TR23-038
| 28th March 2023
__

Rahul Ilango, Jiatu Li, Ryan Williams#### Indistinguishability Obfuscation, Range Avoidance, and Bounded Arithmetic

Next

Edward Pyne, Ran Raz, Wei Zhan

Let $\mathcal{L}$ be a language that can be decided in linear space and let $\epsilon >0$ be any constant. Let $\mathcal{A}$ be the exponential hardness assumption that for every $n$, membership in $\mathcal{L}$ for inputs of length~$n$ cannot be decided by circuits of size smaller than $2^{\epsilon n}$.

We ...
more >>>

Arkadev Chattopadhyay, Yogesh Dahiya, Meena Mahajan

We relate various complexity measures like sensitivity, block sensitivity, certificate complexity for multi-output functions to the query complexities of such functions. Using these relations, we improve upon the known relationship between pseudo-deterministic query complexity and deterministic query complexity for total search problems: We show that pseudo-deterministic query complexity is at ... more >>>

Rahul Ilango, Jiatu Li, Ryan Williams

The range avoidance problem (denoted by Avoid) asks to find a string outside of the range of a given circuit $C:\{0,1\}^n\to\{0,1\}^m$, where $m>n$. Although at least half of the strings of length $m$ are correct answers, it is not clear how to deterministically find one. Recent results of Korten (FOCS'21) ... more >>>

Next