0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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$ ...
-2
votes
0answers
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 ...
0
votes
1answer
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, ...
3
votes
0answers
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 ...
-3
votes
0answers
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 ...
4
votes
0answers
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 ...
-2
votes
0answers
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 ...
1
vote
0answers
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 ...
0
votes
0answers
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 ...
5
votes
0answers
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 ...
8
votes
1answer
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 ...
4
votes
0answers
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. ...
0
votes
3answers
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 ...
2
votes
2answers
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 ...
3
votes
0answers
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 ...
10
votes
2answers
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 ...
1
vote
2answers
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 ...
4
votes
0answers
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$ ...
1
vote
1answer
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 ...
1
vote
0answers
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}}$?
2
votes
0answers
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 ...
0
votes
0answers
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 ...
-2
votes
0answers
23 views

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

Is there a diagram illustrating their relationships?
-4
votes
0answers
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 ...
7
votes
1answer
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 ...
2
votes
0answers
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 ...
3
votes
1answer
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 ...
6
votes
0answers
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 ...
-3
votes
0answers
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 ...
6
votes
0answers
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 ...
14
votes
3answers
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 ...
1
vote
1answer
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 ...
5
votes
0answers
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 ...
1
vote
0answers
45 views

Follow the Perturbed Leader for nonlinear cost functions

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 ...
-1
votes
0answers
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 ...
-2
votes
0answers
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 ...
6
votes
4answers
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 ...
1
vote
1answer
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 ...
2
votes
0answers
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)?
2
votes
1answer
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 ...
5
votes
1answer
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 ...
-4
votes
0answers
46 views

Is Software Consist Weight [closed]

i am confuse about that Is software consist Weight or not? Regards, Arif
-4
votes
0answers
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 ...
1
vote
0answers
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$ ...
5
votes
1answer
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 ...
-4
votes
0answers
27 views

Finding a maximum bipartite matching in O((|A| + |B|)^1.5) [closed]

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. ...
0
votes
0answers
54 views

Expressive enough to talk about Turing machines / Peano arithmetic?

In answering a question about Gödel and Church-Turing: The relation of Gödel's Incompleteness Theorems to the Church-Turing Thesis Andrej Bauer offered "a philosophical answer that may ...

15 30 50 per page