# Questions tagged [computer-science]

For question borderline with, or having application to, computer science. Consider also posting http://cs.stackexchange.com/ or http://cstheory.stackexchange.com/ instead of here, if appropriate.

573 questions
Filter by
Sorted by
Tagged with
64 views

### $\omega$ incompleteness of $\lambda$ calculus

In Plotkin's 'The $\lambda$-Calculus is $\omega$-Incomplete' (The Journal of Symbolic Logic Vol. 39, No. 2 (Jun., 1974), pp. 313-317), an example is given of two (untyped) $\lambda$-terms $M$ and $N$ ...
60 views

133 views

1 vote
76 views

### Understanding statement about bounds of vector in the context of a RSDF ≤ₘ WOPT proof

I'm trying to follow the proof of Lemma 4 of "Strong NP-Hardness of the Quantum Separability Problem", by S. Gharibian, 2010 , which, roughly, states that there is a many-one reduction ...
66 views

### When does Le Cam's method give tight lower bounds for distribution testing?

In the context of statistical estimation or distribution testing, Le Cam's method is a way to prove lower bounds on the minimax sample complexity ([1,2,3,4], further details below). My question is: ...
1 vote
50 views

### Optimal number of half-spaces in H-representation of convex-hall of $n$ points in $\mathbb R^d$

Let $P$ be the polytope obtained as the convex hull of $n$ points in $\mathbb R^d$. This is the $V$-representation of $P$. Note that $P$ can also be represented as an intersection of closed half-...
21 views

129 views

### Is factorial computation known to be in a class smaller than $FEXP$?

Functional version of the counting hierarchy is $FCH$. It is an open problem whether there a sequence of $poly(log(n))$ number of $+,\times$ operations utilizing the assistance of $O(1)$ number of ...
72 views

### Efficient Algorithm to Find Subset of Vectors Over $\mathbb{F}_q$ Living in Low Dimensional Subspace

Let $q$ be a fixed prime, $P, Q$ be polynomials with $\mathrm{deg}(Q) < \mathrm{deg}(P)$ and $h = O(\log n)$. Let $S$ be a subset of $\mathbb{F}_q^n$ of size $P(n)$ such that there exists a subset ...
171 views

### Why is this nonlinear transformation of an RKHS also an RKHS?

I came across this paper (beginning of page 6) where they stated that if $f,h\in \mathcal{H}$, where $\mathcal{H}$ is an RKHS, then $l_{h,f}=\left|f(x)-h(x)\right|^q$ where $q\geq 1$ also belongs to ...
412 views

### How does the greedy algorithm for CSES problem collecting numbers work? [closed]

The collecting numbers problem in the CSES problem set has a greedy solution where we compare the position of a number x with the position of x-1. If pos(x) < pos(x-1) then we increment rounds ...
169 views

### Are there some algorithms which have high consistency strength?

Are there some algorithms, their time complexity is relatively good, for example polynomial time. And the correctness of them has high consistency strength. And these algorithms shouldn't able to ...
49 views

### Logical operations expressed as polynomials

Suppose that $x,y\in\{0,1\}\subset \mathbb{F}$, where $\mathbb{F}$ is a field, which can be assumed of characteristic 0 or arbitrarily large. It is plain that the standard logical operations can be ...
346 views

### Does the morphism of composition have some universal property?

Let $A$, $B$ and $C$ be three objects in the category Set. For simplicity, assume that their underlying sets contain a finite number of elements, a, b and c respectively. Using the usual Haskell ...
5k views

### Revisiting the unreasonable effectiveness of mathematics

Question: On balance, with theoretical advances in algorithmic information theory and Quantum Computation it appears that the remarkable effectiveness of mathematics in the natural sciences is quite ...
172 views

187 views

### Algorithmically decide if an algorithm has optimal time complexity [closed]

Is there an algorithm with the following input and output? INPUT: an algorithm computing a function $\mathbb{N}\to\mathbb{N}$. The algorithm is guaranteed to halt on all inputs. OUTPUT: "YES"...
292 views

### Maximize sum of edge weights on spanning tree

Problem: Given a complete graph with n vertices, the edge weight between vertex $i$ and vertex $j$ is $b[i]\times b[j]$. Under the condition that the degree of point $i$ on spanning tree is DEG $[i]$, ...
580 views

### Is there a term for a subgraph which includes all the edges of a graph?

A subgraph is called spanning when it includes all of the vertices of the given graph. Is there a term for a subgraph which includes all the edges of a graph? Thanks.
219 views

### Games and the right mathematical framework for GANs

Generative Adversarial Networks were introduced in http://papers.nips.cc/paper/5423-generative-adversarial-nets and has more than 20000 citations. It is an important topic within deep learning. Are ...
1 vote
50 views

### Polynomial sized arithmetic map from circle to ellipse preserving integral points

Let $n$ be a square free integer and a product of $O(m/\log m)$ number of primes $1\bmod 4$ where $m$ is $\log_2n$. Take the circle around origin of radius $n^2$. It has ${\exp}(m/\log m)$ number of ...
530 views

### Does there exist a process to build a list of numbers whose standard deviation is an integer?

Or rephrased, is there a way to make a list of numbers whose sample variance is a square number? I'm interested in sequences of arbitrary length with integer elements. (I come from a computer science ...
Given a 'count in range' query access to an array of $N$ elements, our goal is to find $K$ missing elements with as few queries as possible (worst case, deterministic). To clarify, we can query how ...
Let $F\subseteq C([0,1]^n,\mathbb{R})$ be a finite family of functions, which is non-empty. Let $A,B$ be subseteq of $[0,1]^n$, again non-empty, and let $Rad(C)$ denote the Rademacher complexity of ...