All Questions

0
votes
0answers
2 views

What is the relationship between “model of computation” and “algorithm”?

Traditionally, the usual definition you find for model of computation is "an abstract description of how a computation may be carried out". To me, this seems really close to the informal notion of ...
3
votes
0answers
43 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$ ...
6
votes
2answers
125 views

Is uniform convergence faster for low-entropy distributions?

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 $\...
1
vote
1answer
41 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 ...
7
votes
1answer
157 views

Can a totality checker be used to guarantee a proof on the calculus of constructions + inductive types is correct?

If we extend the Calculus of Constructions with Fix, we gain a lot of expressivity for barely no added complexity. That includes being able to derive induction, perform large eliminations, prove ...
5
votes
2answers
135 views

Is getting post-doc difficult in theoretical computer science with few published papers?

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

Is this a knapsack problem?

I have a set of $K$ keywords. Each of this keywords can have set of bids from $1\$,\dots,N\$$. For each bid for a keyword, it will get a specific amount of clicks and a specific cost. Clicks and Cost ...
0
votes
1answer
58 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" ...
0
votes
0answers
12 views

Partial Recursive Functions of Kleene [on hold]

I am writing and asking for your help, if you could give me any good sources for the topic which is in the title. I have to do a powerpoint presentation this week and I really couldn't find any ...
9
votes
2answers
5k views

Time complexity of Held-Karp algorithm for TSP

When I looked through "A Dynamic Programming Approach to Sequencing Problems" by Michael Held and Richard M. Karp, I came up with the following question: why the complexity of their algorithm for TSP ...
-1
votes
0answers
33 views

Alternate proof for network flows property (network flow = flow across cut)

I have an alternate proof of Lemma 26.4 of Cormen etal's book, Third Edition. Would appreciate critiques or comments on correctness. Terminology of Corman etal book on Introduction to Algorithms, ...
3
votes
1answer
50 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 ...
2
votes
1answer
86 views

Applications of Christol theorem

I'm looking forward to know about applications of Christol theorem mentioned in Jefrrey Shallit's Number theory and formal languages. One of them is purely algebraic: if $f, g \in \mathbb{F}_q[[z]]$ ...
5
votes
0answers
105 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 ...
18
votes
0answers
542 views

Identifying Reducible/Irreducible polynomials over $Z[x]$

It is well known LLL algorithm provides a fully polynomial algorithm to factor a reducible primitive polynomial over $\mathbb{Z}[x]$. Say one only seeks to identify whether a given polynomial over $\...
-2
votes
0answers
22 views

Turing machine with semi infinite tape - Prove by construction [on hold]

I'm studying constrained Turing Machines. There's a theorem that proves that both infinite and semi-infinite tape TM have the same computational power. The theorem that proves this by emulating a TM1 ...
-3
votes
0answers
71 views

Difficulty Grasping Asymptotic Notation in CLRS Algorithms Book [on hold]

While reading the Amortized Analysis chapter of the CLRS book, I encountered the following. Since each of these operations runs in $O(1)$ time, let us consider the cost of each to be 1. The total ...
1
vote
1answer
67 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 ...
2
votes
1answer
253 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 ...
0
votes
0answers
24 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 ...
2
votes
1answer
85 views

Is there a gap between weak learning and PAC-learning?

For concreteness lets use the definitions of PAC and weak-learning as in the notes of Avrim Blum (http://www.cs.cmu.edu/~avrim/ML12/lect0208.txt) and also his notes on SQ-Learning (http://www.cs.cmu....
4
votes
1answer
528 views

Knapsack with dependent profits (pairs of items)

I'm working on a problem which MAY be reduced to the following version of Knapsack: Suppose two items $e_i$ and $e_j$ have profit $p_i$ and $p_j$ respectively. However, if both items are present in ...
3
votes
1answer
195 views

Finding self-similar homomorphisms of a FSM transducer

Consider a special case of homomorphisms of FSM transducers (or "generalized sequential machines" in [1]). Let $F$ be a transducer accepting a language $L$, and let $h(x)$ be a homomorphism function ...
10
votes
2answers
1k views

Is compiler for dependent type much harder than an intepreter?

I have been learning something about implementing dependent types, like this tutorial, but most of them is implementing interpreters. My question is, it seems that implementing a compiler for ...
-1
votes
0answers
78 views

What kinds of algorithm have running time $O(\log n/ \log \log n)$in most of the cases? [closed]

I'm curious that what kinds of algorithm have running time $O(\log n/ \log \log n)$in most of the cases. Since I'm working on a project that requires speedup for algorithms, I need general knowledge ...
48
votes
17answers
12k views

Most memorable CS paper titles

Following a fruitful question in MO, I thought it would be worthwhile to discuss some notable paper names in CS. It is quite clear that most of us might be attracted to read (or at least glance at) a ...
1
vote
0answers
34 views

A categorized (?) list of functional pearls in JFP and ICFP

Is there a list of (categorized preferred) functional pearls ever published in ICFP and JFP? I could go to the ICFP proceedings and JFP issues and find all of them, but this would be time-consuming. ...
-3
votes
0answers
29 views

Map Reduce and Sorting [closed]

Suppose we have the following input: $$ \text{name} \ \ \ \text{count} \\ \text{adam} \ \ 10 \\ \text{apple} \ \ 50 \\ \text{apricot} \ \ 50 $$ If we implement a $\text{Mapper}$ that emits $(\text{...
7
votes
2answers
301 views

Are all turing machines paths predictable?

I was recently studying partial solutions to the halting problem and came across the problem which I discuss below. In particular I was studying when it was computable to tell if a turing machine has ...
-1
votes
1answer
67 views

When is extra vertex required in arbitrage detection using Bellman Ford?

I am studying applications of shortest path, in particular arbitrage. Specifically, I was reading these two resources: https://stackoverflow.com/questions/2282427/interesting-problem-currency-...
1
vote
1answer
112 views

Does every online algorithm has an offline counterpart?

According to the wikipedia page for Online algorithms, it states: "Not every online algorithm has an offline counterpart." At the time of asking this question there is no citation for this claim. ...
-6
votes
0answers
46 views

who is able to solve that paper [closed]

Exams Determine the time complexity of the following program statement in java for (int i = 10; i < 20; i = i+ 1) { for (int j= 10; j < 20; j = j + 1) { Y=(a(i,j) ^2 )+5; System.out....
-1
votes
0answers
45 views

Find optimum of a neural network computationally

Imagine a neural network, whose parameters (like number of layers, epochs of training, numbers of neurons, ...) can be specified as arguments. You don't know where the optimum is (say, the point where ...
1
vote
1answer
66 views

Pulling a graph across a partition

I am looking for the name for a particular graph property, if it has been studied, and efficient algorithms for computing it, if they exist. I realise that this may be a well known property that I am ...
1
vote
0answers
73 views

Impartial Combinatorial Games as a core of the final undergraduate project

Solving several problems of Impartial Combinatorial Games in Game Theory has drawn my attention. So that, I'd like to ask if it's possible to use this topic (e.g. Sprague Grundy theorem) as a core or ...
1
vote
0answers
44 views

Ordering tours in a Euclidean TSP according to (strictly) increasing length

Let $H$ be the set of all Hamiltonian cycles on the complete graph $K_n$ associated with a set of $n \geq 4$ points $P$ in the plane where edge weights are defined using the Euclidean distance between ...
-1
votes
0answers
28 views

Do new algorithms or better machine learning methods have a better chance of making an impact on protein analysis in bioinformatics?

In other words, are new classic algorithms critical to bioinformatics or are they sort of a commodity now, providing small constant factor improvements to analysis runs, but not contributing ...
1
vote
0answers
55 views

Complexity of enumerating over promise problems and circuits?

Given an enumeration over all Turing Machine which run with increasing length, is there a ``complexity class'' which describes the complexity of determining whether a given TM satisfies the promise ...
-2
votes
1answer
162 views

Graduate school for CS theory?

I am currently studying a bachelor's in (joint honours) Mathematics and Computer Science in the UK. I am intrigued by the sorts of problems present in theoretical computer science and I want to ...
9
votes
0answers
71 views

Are there cascade decompositions of machines that are more general than finite automata?

The idea of decomposing automata and their associated semi-groups into irreducible sub-components is due to Krohn & Rhodes and has been explored relatively thoroughly. Krohn & Rhodes gave an ...
1
vote
0answers
85 views

Solving the Halting problem for most inputs [closed]

Is it possible to solve the following version of the Halting problem : given any Turing machine and some input tape, the program should answer if this pair halts or not except possibly for one Turing ...
2
votes
1answer
63 views

Find shortest prefix to generate original string by overlapping

Given a string $S$, I want to find the prefix string $P$ of shortest length, such that the original string $S$ can be generated by concatenating copies of $P$ (where overlapping is allowed). For ...
-1
votes
0answers
48 views

how to calculate inverse of entropy?

I was wondering how to calculate the inverse of a binary entropy function, seems very simple but iI don't think that the answer I get is correct (i get 1.1461). this is what i want to do: p should ...
0
votes
0answers
63 views

What is the formal statement of the dining philosopher's problem? [migrated]

I've read about it in a few places and I'm not sure I get it. Are the philosopher's allowed to act simultaneously? Do they each take 1 action simultaneously, then go on to their next action?
2
votes
1answer
88 views

Sample Complexity for Order Statistics

I have a sample complexity question which seems fairly basic, but for which I'm having trouble finding a reference. Let $F$ be an unknown distribution over $[0,1]$. Denote by $X_{k:n}$ the $k$th of $...
3
votes
0answers
70 views

Do features always induce a metric?

It is well-known in functional analysis that an inner product always induces a norm and a norm always induces a metric, and the reverse directions do not hold in general. I am wondering if a similar ...
1
vote
1answer
66 views

Cryptography protocols using graph problem instances

I personally am only aware of basic examples of public key cryptography and I haven't studied cryptography yet. I'm curious if there are circumstances in cryptography where using problem instances ...
4
votes
1answer
71 views

What is the current state of the art in black-box grammar induction?

Grammar induction of Context Free Languages seems to be a very well researched field. I would like to know the current state of the art in inducing a Context Free Grammar (I am reading up Higuera's ...
1
vote
0answers
40 views

how to achieve a topological sort of an given sequence with minimum swaps

For example, given the constraints {$a<b,c<d$} and a sequence $[b,a,c,d]$. we just need swap $a$ with $b$ to get an topological sort, I want to ask how to find the sort solutions with minimum ...
14
votes
2answers
332 views

Collapses under the assumption that $NEXP\subseteq P/Poly$

It is known that if $NP\subseteq P/Poly$ then the polynomial hierarchy collapses to $\Sigma_2^{P}$ and $MA = AM$. What are the strongest collapses known to happen if $NEXP\subseteq P/Poly$?

15 30 50 per page