# All Questions

3 views

### Identifying ambiguities in inductively learned concepts

I'm looking at ways in which "ambiguities" can be identified in labeled training data by a system undergoing some sort of inductive learning process. Do you know if there is any literature on this ...
4 views

### Can we verify satisfiability of first order statements via saturation in sub-exponential time?

In first order logic, we can prove satisfiability several ways: Finite model generation, truthful monadic abstractions, and also saturation. With finite model generation techniques, we can verify the ...
13 views

### Bisection Width of a Mesh Topology

What is the bisection width of a q-dimensional mesh topology with one dimension having k nodes, where bisection width splits the network as evenly as possible into two sets (with a difference of at ...
22 views

### Alternating tree automata for arbitrary arity tree

Could alternating tree automata be used for recognizing set (language) of arbitrary-arity trees? More specifically, as an example: let $\Sigma = \{a,b,c\}$ - labels for tree nodes. Trees from $T$ ...
23 views

### example for context free language which satisfy the pumping lemma [on hold]

I'm a beginner to Automata Theory. I found this interesting topic pumping lemma. I know to prove a language is not a context free using pumping lemma. But I didn't found any example for context free ...
33 views

### Quantum Computing & Ray Tracing Rendering Engines

As a non-expert in any of these fields, but out of interest, I have been looking into basic concepts of quantum computing. And I was wondering, taking the concept of ray tracing and rendering engines, ...
46 views

### Time complexity of a branching-and-bound algorithm

Theoretical computer scientists usually use branch-and-reduce algorithms to find exact solutions. The time complexity of such a branching algorithm is usually analyzed by the method of branching ...
30 views

### Karp reduction/many-one reduction [on hold]

Why is Karp reduction also called "many-one reduction"? What do the 'many' and the 'one' stand for? I tried looking at wikipedia and read some books but I did not find any explantion. I do understand ...
40 views

### Logics for timed resource control

I'm studying proof theory and I've seen that linear logic can be used as a way to control resource usage, since by the propositions-as-types it is equivalent to the linear lambda calculus. Is there a ...
45 views

### Numerical eigenbasis for a unitary

Do you know what numerical software computes an eigenvector basis for a unitary matrix? Say I have a unitary matrix $U$. If its eigenvalues are simple (no multiplicities), then for instance Matlab ...
32 views

### How and why does Recrypt function works?

The general aproach presented by Craig Gentry in 2009 to create a fully-homomorphic encryption system is roughly the follow: Create a scheme that can evaluate some functions (increasing the noise in ...
36 views

### How many maximization algorithms can we run at the same time on a simple (or super) computer? [on hold]

I have a maximization problem which consists of finding the max of $2^L$ elements. This can be done in $O(2^L)$. This problem can be decomposed into $L$ maximization problems, where solving problem ...
72 views

### Quantum algorithms for QED computations related to the fine structure constants

My question is about quantum algorithms for QED (quantum electrodynamics) computations related to the fine structure constants. Such computations (as explained to me) amounts to computing Taylor-like ...
119 views

### “Snake” reconfiguration problem

While writing a small post on the complexity of the videogames Nibbler and Snake; I found that they both can be modeled as reconfiguration problems on planar graphs; and it seems unlikely that such ...
85 views

### Recognizing sequences sortable by transpositions?

While reading the post, Probability of generating a desired permutation by random swaps, by Scott, I got interested in this problem of sorting: Input: a sequence $A$ of $2N$ positive integers. ...
288 views

### How could God authenticate in one message?

Thought experiment: Which data could convince experts, beyond reasonable doubts, about their origin outside our universe? From which margin should an expert consider such claim seriously? For ...
191 views

### Counting occurences of 'a' in a book faster than O(n)? [on hold]

I was asked the following question in an interview: How would you count the occurrences of character a in a 500-page book? For simplicity, assume that you are ...
47 views

### Low-degree testing in PCP Theorem using bivariate polynomials

I read about modifications of the low-degree test used in the (first) proof of the PCP theorem. The test used in the proof works over randomly chosen lines while modifications allow choosing random ...
123 views

### Pseudorandom generator for finite automata

Let $d$ be a constant. How can we provably construct a pseudorandom generator that fools $d$-state finite automata? Here, a $d$-state finite automata has $d$ nodes, a start node, a set of nodes ...
86 views

### Recommendations for References on undecidability of First Order Logic

I am currently reading Computability and Logic by Boolos Burgess Geoffrey for the proof on "undecidability of first order logic". however, I find the notations a bit confusing. Can anyone recommend ...
136 views
+50

### Lower bound on estimating $\sum_{k=1}^n a_k$ for non-increasing $(a_k)_k$

I'd like to know (related to this other question) if lower bounds were known for the following testing problem: one is given query access to a sequence of non-negative numbers $a_n \geq \dots\geq a_1$ ...
64 views

### Is there notation for converting a multi-set to a set?

Suppose we have a multi-set $S$. For example, $S = \{ 1,2,2,3 \}$. Suppose we also have a set $T$, e.g., $T=\{1,2,3\}$. I would like to say, compactly, that $S$, when its duplicates are removed, is ...
45 views

### Discrepancy of Hadamard type matrix

Let $H$ be $\{-1,+1\}$ Hadamard matrix of size $2$ and $J$ be the same size all $1$ matrix. Let $W$ be $\frac{H+J}{2}$. Is the discrepancy of $W^{\otimes k}$ atmost $\sqrt{k^{-1}}$?
120 views

### Subset sum solver. Worth continue working on this method? [on hold]

I have been working in a subset sum problem solver for some time. The implementation is an exact/exhaustive search solver. The variable determining the asymptomatic growth rate is just $N$ (the ...
34 views

### Total number of spanning trees of a set of graphs with constraint

This is an extension of the question "Total number of spanning trees of a set of graphs". The original problem has been shown to be #P-complete. Now a new constraint is added to the problem. I have ...
23 views

### What is the relationship between regular, context free and computable language? [on hold]

Is there a diagram illustrating their relationships?
23 views

### Quick question: What does it mean for a language to be “recognized” by an automaton? [on hold]

I am not particularly familiar with the usage of "recognized" in English, can explain what this means for a language be recognized by an automaton? Does it mean that the NFA, DFA, Pushdown or Turing ...
312 views

### Does $NP$-hardness of $c$-approximation (for some $c>1$) imply $APX$-hardness?

Assume that for a given minimization problem with only integer solutions, it is $NP$-hard to decide if the optimal solution is 5 or 6. I.e., a polynomial-time algorithm with an approximation ratio ...
23 views

### Concept of 'shape' in clustering

Is there any abstract definition for 'shapes' of a cluster? I am currently working on providing for a set of axioms to study clustering. In my work, I have found a need for an abstract definition for ...
53 views

### What are the major research issues in distributed transactions?

Background: Transaction processing has been a traditional research topic in database theory. Nowadays distributed transactions are popularized by the large-scale distributed storage systems which ...
73 views

### Maximum weight “fair” matching

I'm interested in a variant of the maximum weight matching in a graph, which I call "Maximum Fair Matching". Assume that the graph is full (i.e. $E=V\times V$), has even number of vertices, and that ...
30 views

### Implementation of Min Max Matching in Christofides algorithm for approximating TSP

How is the corresponding step of finding the minimum-cost perfect matching on the odd-degree nodes is supposed to be implemented? The induced graph is not bipartite and all the algorithms I know for ...
81 views

### Examples of open problems solved through application of a theorem already known

Are there good examples of reasonable open problems in TCS that had an 'obvious' solution via application of a theorem found in mathematics probably found a few decades earlier but went unnoticed in ...
191 views

### Can typed lambda calculi express *all* algorithms below a given complexity?

I know that the complexity of most varieties of typed lambda calculi without the Y combinator primitive is bounded, i.e. only functions of bounded complexity can be expressed, with the bound becoming ...
38 views

### Are (empirical) Rademacher complexity always positive?

Rademacher complexity and empirical Rademacher complexity are used to provide upper bound on the loss of solving an learning problem. That seems to imply that Rademacher complexity and empirical ...
55 views

### Is there a purely functional vector with O(1) access to the front and back but O(log n) concatenation?

Context: For fun and perhaps for actual use, I'm making my own programming language that would compile to Typed Racket, a statically-typed Lisp dialect. One of the major features I want to implement ...
45 views

The famous FTPL algorithm [1] is analyzing linear cost function. Is there any generalized proof for nonlinear functions known? Note that in the last paragraph of [1] it says "It would be great to ...
12 views

### determing the max flow with only edge capacities from n/w with additional vertex capacities?

Let ((V, E); s, t; c) be an extended flow network where not only edge capacities, but also vertex capacities are constrained, i. e., c : E ∪ V → R^ + 0 and a flow f : E → R^ + 0 must satisfy, in ...
33 views

### FPTAS for bin packing

If an algorithm for bin packing has a guarantee of OPT(I)+log^2(OPT(I)), then there is a fully polynomial approximation scheme for this problem. I have to prove this statement, but I have no idea ...
218 views

### Finding a permutation $p$ of $x_1, x_2, \dots, x_n$ which maximises $\sum_{i=1}^{n-1}|x_{p_{i+1}}-x_{p_i}|$

Here is the algorithmic problem I'm trying to solve: Given a list of integers $x_1, x_2, \dots, x_n$ find a permutation $p_1, p_2, \dots, p_n \in [n]$ that maximises the sum ...
69 views

### What is known about matrix multiplication, and matrix circuits?

So I'm wondering, first off, where I can read up to get a feel for state-of-the-art matrix multiplication concepts. I'll try to be more specific: I'm wondering if there has been research on circuits ...
81 views

### Known algorithms for Graph isomorphism [closed]

What algorithms are known for the graph isomorphism problem? Can those algorithms be related to algorithms for other graph theoretical problems (e.g. subgraph problem, counting graph isomorphisms)?
103 views

### The relationship between QCMA and QMA in the Turing and Communication model

First my background about computational complexity is still beginner. Recent paper published by Klauck and Podder [KP14] show that for the first time an exponential gap between computing partial ...
57 views

### What is the state of the art research in analysing algorithms on GPU architectures?

I have found many papers on sequential algorithms that have been implemented and tested on GPU architectures. Each of these papers usually as a result contains the amount of speedup that was achieved ...
46 views

### Is Software Consist Weight [closed]

i am confuse about that Is software consist Weight or not? Regards, Arif
29 views

### Pygame Countdown time [closed]

Can anyone help me with creating a timer in pygame? I have a game where I would could like to have a timer for someone to complete the game. this is what I have def countdown(countdown): for t ...
20 views

### Rate of convergence of graph-theoretic quantity to fractional graph-theoretic counterpart

Let $G^n$ denote the OR product of a graph with itself $n$ times, i.e. the graph which has an edge between distinct vertices $(v_1,v_2,\ldots,v_n)$ and $(u_1,u_2,\ldots,u_n)$ if there exists some $i$ ...
84 views

### What is the worst-case runtime complexity to transform a NFA to DFA via Rabin-Scott's power set construction?

What is the worst-case runtime complexity to transform a NFA to DFA via Rabin-Scott's power set construction? Why? Details: http://en.wikipedia.org/wiki/Powerset_construction states that the ...
I aim to solve the following puzzler I recently read: A toymaker is faced with a group of $|A|$ buyers for their stock of $|B|$ distinct toys. Each buyer can buy up to 3 toys if available for buying. ...