# All Questions

11,527 questions
Filter by
Sorted by
Tagged with
17 views

### What is the analog of PPAD and TFNP for Logspace?

What are the analogs of PPAD and TFNP for logspace? Is any of these known to be in $FL$?
12 views

### polynomial over a field

Example: P = a(xy) + b(x^2y) + c(yz^3) + .... when speaking of a "polynomial over a field F" does one mean that the coefficients (a, b, c,...) are drawn from the field F, or the variables (x,...
15 views

### k-Median Problem With Restricted Centers

The $k$-median problem is defined as follows: Given a set $C$ of clients and a set $L$ of facility locations defined over a distance metric $d$. Open a set $F$ of $k$ facility in $L$ such that the ...
26 views

172 views

### Upper bound on the expected number of correct bits via a "lossy compression"

Consider the following "compression problem" for a pair $(C,D)$ of algorithms: $C$ receives a uniformly random $x \in \{0,1\}^n$ and outputs a smaller bit string $y \in \{0,1\}^s$. Algorithm ...
108 views

### Can this NP-hardness proof for Super Mario Brothers (and other games) be simplified?

In "Classic Nintendo Games are (Computationally) Hard", a generalized framework based on reducibility of 3-SAT for proving NP-hardness of classic Nintendo games is presented, and several ...
108 views

### Can exponential-size depth-2 $CC^0[m]$ circuits with generalized $MOD_m$ gates compute arbitrary functions from $Z/mZ$ to $Z/2Z$?

Terminology $CC^0[m]$ is the set of polynomial-sized, constant depth circuits consisting entirely of $MOD_m$ gates for some $m \geq 2$, where a $MOD_m$ gate outputs a 1 if and only if the sum of its ...
81 views

### Why is the ellipsoid method numerically unstable?

In the Ellipsoid method wikipedia entry under the performance section, it is mentioned that the Ellipsoid method often times is numerically unstable in practice: "On even "small"-sized ...
81 views

### Maximally Permissive Strategies for Safety Properties

Different definitions of maximally permissive strategies exist. For instance, in (Bernet, Janin, and Walukiewicz 2002), strategies are compared by looking at inclusion of the behaviors/outcomes they ...
37 views

### Is it possible to count the total number of local minima for a scalar, multivariate function?

We can assume the function is differentiable, but it is also non-convex and setting the gradient equal to zero has no analytical solution. We can also assume that the domain is bounded, namely the ...
47 views

### Decision tree vs. pebble game lower bounds

This question concerns two types of lower bounds. In a pebbling lower bound, we are concerned with the complexity of constructing the output from the input. For example, if the only way we could ...
57 views

### Exact FPT Algorithm for Continuous Euclidean $k$-Means

The continuous Euclidean $k$-means problem is defined as follows: Given a set $X$ of $n$ points in $d$ dimensional Euclidean space $\mathbb{R}^{d}$. Given a parameter $k>0$, find a partitioning $P$ ...
20 views

### Fast algorithms for convex-convex quadratic fractional programming

What are the fastest algorithm(s) (possibly approximation algorithms) for solving convex-convex quadratic fractional programming problems, i.e. optimization problems of the form  \begin{align*} \sup&...
### $\mathbf{AC}^0$ lower bounds for $\mathsf{Gap}\text{-}\mathsf{Max3SAT}$
Various gapped maximization problems are known not to be $\mathbf{NP}$-hard under $\mathbf{AC}^0$ reductions, e.g., $\mathsf{Gap}_{1,\epsilon}\text{-}\mathsf{Max3SAT}$ (see, e.g., Proposition 4 of ...