All Questions

1
vote
0answers
8 views

Stable order on binary strings

I need some order on binary strings such that if I have a small (but superlinear in their length) number of sufficiently different strings, the order will stay the same if I change a few bits in the ...
0
votes
0answers
21 views

Newman's lemma for distributional communication complexity

This may be obvious — sorry if it is. Newman's lemma (Newman91] shows that any public-coin communication protocol to compute a Boolean function $f\colon \{0,1\}^n\times\{0,1\}^n\to\{0,1\}$ can be ...
0
votes
0answers
8 views

Theoretical Model for Quantum EBC, Holographic Electron Black hole Entropy Computational System

Black Hole Thermodynamics, Blackhole Entropy, Blackhole Information Paradox, Einstein Bose Condensate’s & Quantum 3D Photonics Quasicrystal Circuits suspended in EBC (Einstein-Bose Condensate, ...
0
votes
1answer
16 views

Is a reference on T a subtype of T?

If I take the book Practical Foundations for Programming Languages by Robert Harper, the following definition is given for subtyping: A subtype relation is a pre-order on types that validates the ...
0
votes
0answers
20 views

Back-propagation for computing derivative of certain line integral

Consider a function F (think of neural networks) with two sets of parameters: (1) model parameters $\mathbf{w}$, and (2) input data ${\bf x} \in {\mathbb R}^d$. Fix $i \in [d]$, consider the following ...
0
votes
0answers
50 views

If a quantity is uncomputable does that mean that its value does not exist in Nature? [on hold]

In [1], Scott Aaronson thinks about what NP-completeness can tell us about nature. Like some problems are NP-complete, some problems are uncomputable. Following Aaronson's way of thinking, we may ...
0
votes
0answers
20 views

Best approach for allocation problem

I am a bit rusty on optimization algorithms and need an advice. This is my problem: I have n images (with width and ...
0
votes
0answers
67 views

EXPSPACE proof and its implications

I'm dealing with the min-max regret 0-1 Integer Linear Programming problem (MMR-ILP, for short), which is formulated as below. \begin{equation} \label{eq:nip_obj} \min_{x \in \Phi} \sum_{i = 1}^n ...
4
votes
1answer
110 views

Complexity of Acyclic Hypergraph Isomorphism

It is well known that the graph isomorphism problem restricted on trees is much easier than the general case. It can be done in logarithmic space (Jenner B, Lange KJ, McKenzie P. "Tree isomorphism and ...
4
votes
2answers
105 views

Are there hypothesis classes that are hard to learn but easy to test?

Let $H$ be a binary hypothesis class, it is easy to see that if $H$ is (efficiently) properly PAC learnable then it is also (efficiently) testable (here we use the standard notion of within or $\...
-2
votes
0answers
50 views

Distance vector vs Link state routing

i do know the differences and advantages and disadvantages associated with link state and distance vector routing algorithms. But i was unable to answer the question " when should i use distance ...
6
votes
1answer
143 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$ ...
0
votes
0answers
49 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 ...
5
votes
2answers
204 views

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

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
15 views

Partial Recursive Functions of Kleene [closed]

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 ...
0
votes
1answer
90 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" ...
6
votes
2answers
172 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 $\...
2
votes
1answer
58 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 ...
3
votes
1answer
57 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 ...
5
votes
0answers
133 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 ...
-2
votes
0answers
27 views

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

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
74 views

Difficulty Grasping Asymptotic Notation in CLRS Algorithms Book [closed]

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
70 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 ...
0
votes
0answers
31 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
275 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 ...
2
votes
1answer
91 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....
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. ...
4
votes
1answer
98 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]]$ ...
-1
votes
1answer
68 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
votes
0answers
46 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
69 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
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 ...
9
votes
0answers
75 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 ...
-2
votes
1answer
166 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 ...
1
vote
0answers
88 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 ...
1
vote
0answers
56 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 ...
-1
votes
0answers
51 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 ...
2
votes
1answer
64 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 ...
3
votes
0answers
72 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
0answers
42 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 ...
1
vote
0answers
74 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
1answer
68 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 ...
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?
0
votes
0answers
59 views

Function theory and functonal analysis in Computer science

functional analysis and function theory are enough abstract fields of mathematics but they are used in practice for example in physics. I am interested how much they used in computer science, ...
7
votes
2answers
305 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
vote
0answers
45 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 ...
0
votes
0answers
44 views

Isometric Extension of an Erasure Channel [migrated]

Show that an isometric extension of the erasure channel is $$U^N_{A\to BE} =\sqrt{1−\epsilon}\left(|0\rangle_B \langle 0|_A +|1\rangle_B \langle 1|_A \right)\otimes|e\rangle_E+ \sqrt{\epsilon}|e\...
2
votes
0answers
110 views

Crime prevention using graph theory and machine learning

I am looking for a way to the model the incidence of crime among a network of individuals. Part of it will use machine learning, and part of it will have to resort to some graph theoretic ...
6
votes
1answer
98 views

Time complexity of derivative-based regex matchers

Regex matching using the Brzozowski derivative without any caching or expression-simplifying takes exponential time and space because of the product rule. In Brzozowski's original paper, Brzozowski ...
6
votes
0answers
76 views

About assumptions needed to get convergence of stochastic gradient methods on non-convex objectives

What are the minimal conditions we know of under which we can prove that a stochastic gradient based algorithm can convergence to criticality on a non-convex objective? Are there any necessary ...

15 30 50 per page