# All Questions

9,919 questions
47 views

62 views

### Points of a finite set wihtin a ball

I am looking for data-structures to store efficiently a set of points $E$ in an euclidean space of dimension $d$. In particular, I would like to be able to solve the problem of finding all the point ...
101 views

### Can a term on normal form prove an illogical assertion?

Suppose we take a language such as Agda and disable the features that make it consistent; for example, universe polymorphism, structural recursion checks and similar. Suppose then that we take a term ...
36 views

### Optimally fair stable matching

There's a nice post by Gil Kalai which outlines the inherent bias in stable matching algorithms quantitatively. In the traditional loyd shapeley algorithm for $n$ men and $n$ women, given randomly ...
148 views

### Minimal information needed for determine some function

From calculus, we know that if someone has a continuous function $f$, it is enough to know $f$'s values on the rationals in order to know $f$ on the entire line. In some sense, a "countable amount of ...
142 views

### Does BQP contain any NP-Complete problem?

From the Wikipedia documentation, "the suspected relationship of BQP to other problem spaces" diagram suggests no intersection between NP-complete problems and BQP. Has this been demonstrated or not?
26 views

### Does an Earley parser equipped with LL(1)-style lookahead parse in linear time for all LL(1) grammars?

If a standard Earley parser (with proper handling of nullable non-terminals, see Section 4 of "Practical Earley Parsing" by Aycock and Horspool) is modified with LL(1)-style lookahead, does it then ...
39 views

### QMA definition of difference between probabilities intuition

I'm reading about the complexity classes related to quantum computation, currently I'm studying QMA class. A language is in QMA(c,s) if there exists a polynomial time verifier and polynomial $p(n)$ ...
30 views

### PTAS for projective clustering : survey

$(k,j)$-projective clustering is the natural generalisation for k-clustering, in which one needs to find $k$ $j$-flats in $\mathbb{R}^d$ that minimizes the cost function as defined below: Given a $j$-...
77 views

### Is it possible to have a sorting algorithm that computes faster than QuickSort? [closed]

Given an unsorted array, QuickSort has to touch each source element it is trying to sort multiple times before it declares an array as sorted. (notice how many times the 2 is touched [circled in red ...
90 views

### Why is the “general notion of a reduction […] inherent to the notion of self-reducibility”?

While reading "Computational Complexity: A Conceptual Perspective" by Oded Goldreich, I have come across the following passage, which I simply cannot get my head around: Note that the general ...
20 views

### Assumption of unique shortest paths in subcubic reduction

In the paper "Subcubic equivalences between graph centrality problems, APSP and diameter", it is shown that the all pairs shortest path problem (APSP) and the problem of computing the betweenness ...
179 views

### SAT Solvers and their applications

I've been reading and learning about SAT solvers this week. If they can solve problems with thousands of variable quickly haven't we practically solved ANY problem that can be reduced to it, including ...
64 views

### Pop desired elements on stacks of bounded capacity

Consider there are $k$ stacks containing a total of $n$ elements. Each element is either red or blue. We have complete knowledge of each element's location and color. Only push and pop are allowed on ...
76 views

### Can relativization technique be applied to natural NP-complete languages?

Levin [1] defined distNP is the distributional problem (L,D), where L ∈ NP, and D is an ensemble of efficiently samplable distributions over problem instances. We say that a distNP problem (L,D) is ...
41 views

### Are there any continuous-time stochastic processes in which transition probabilities are discontinuous functions over time? [closed]

In stochastic processes, like homogeneous Markov processes, Poisson processes, Queueing systems etc., the functions that represent (transition) probabilities are continuous over time. This is also ...
198 views

### Deciding whether a graph contains a complete balanced bipartite graph

Is it known whether the following problem is in P or is NP-complete? Problem: given an input graph $G$ on $n$ vertices, decide whether $G$ contains a complete $n/2 \times n/2$ bipartite graph.
63 views

### Complexity of low-rank matrix factorizations with rows in a simplex and outliers

Our goal is to obtain a matrix factorization in form of $M = U V'$, where $U\in\mathbb{R}^{d\times r}, V \in\mathbb{R}^{N\times r}$ and each row of $V$ satisfies $$\sum_{j}(V)_{ij}=1, (V)_{ij}\ge 0$$...
52 views

173 views

### Distinguishing a biased coin with a small set of tests

Say we have a "coin" $f : [n] \to \{\pm 1\}$ so that either $f$ is balanced, or $f$ is $\epsilon$-far from being balanced. It's a classic result that sampling $O(1/\epsilon^2)$ random points of $f$ ...
128 views

### Is this a knapsack problem?

I have a set of $K$ keywords. Each of this keywords can have a set of bids from $1\$,\ldots, N\. For each bid for a keyword, it will get a specific amount of clicks and a specific cost. Clicks and ...
255 views

### Is getting post-doc difficult in theoretical computer science with few published papers? [closed]

I am a Ph.D student ( expected to graduate in few months ) works in computational mathematics. In my PhD, I have published just couple of research papers. I am willing to go for a post-doc( US, Europe,...
120 views

### Subset Sum Problem and hard looking instances that are not really hard

I have been working in a subset sum solver (some new approach) and while working on the time complexity analysis I found what I describe below. Maybe this could explain why some "hard looking" ...
184 views

Let $\mathcal D$ be a probability distribution on $\{0,1\}^d$. Let $X_1, \cdots, X_n \in \{0,1\}^d$ be i.i.d. samples from $\mathcal D$. Let $\mu \in [0,1]^d$ be the mean of $\mathcal D$ and let $\... 1answer 87 views ### Strong Normalization of Extended Calculus of Constructions (CC with cumulative universes) There are some proofs around to prove the strong normalization of the calculus of constructions (i.e. that all type systems in the lambda cube are strongly normalizing). I have analyzed the proof ... 1answer 60 views ### Distinguising between the cases of low or high cover number Is there a known result saying that for some constants$0 < a < b < 1$, it is NP-hard to distinguish a graph having vertex cover number at most$a \cdot n$from a graph having vertex cover ... 1answer 188 views ### Evaluation of an arithmetic formula where the time depends on the length of the arguments of gates Let$(X,+,\cdot)$be a commutative ring. Let$|\cdot|\colon X\to \mathbb{N}$be a function that satisfies$|x+y|\leq |x|+|y|$and$|xy|\leq |x|+|y|$. We call the function length, and length is always ... 1answer 76 views ### Is balanced Hamiltonian cycle NP complete on maximal plane graphs? I know that the Hamiltonian cycle is NP complete on the class of maximal plane graphs. If we instead ask about balanced Hamiltonian cycles (i.e. same number of faces on both sides) on maximal plane ... 0answers 37 views ### What is the right term/theory for prediction of Binary Variables based upon their continuous value? I am working with a linear programming problem in which we have around 3500 binary variables. Usually IBM's Cplex takes around 72 hours to get an objective with a gap of around 15-20% with best ... 1answer 318 views ### Is there a counterexample to this work? Is there a counterexample to this claim https://arxiv.org/abs/1610.00353? They claim a$O(n^6)\$ LP model with simulations to support. I think asking validity is not a reasonable problem. However ...

15 30 50 per page