# All Questions

9,928 questions
56 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 ...
36 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 ...
35 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 ...
267 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. \label{eq:nip_obj} \min_{x \in \Phi} \sum_{i = 1}^n ...
136 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 ...
133 views

97 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 ...
62 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 ...
218 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 ...
84 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 ...
378 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 ...
104 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....
41 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. ...
109 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]]$ ...
74 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-...
76 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 ...
83 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 ...
197 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 ...
98 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 ...
62 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 ...
72 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 ...
86 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 ...
61 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 ...
76 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 ...
75 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 ...
328 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 ...
48 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 ...
118 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 ...
107 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 ...
94 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 ...
48 views

### Why do k min-hashes, instead of one hash where we find the k minimum elements?

Traditionally if one wants to sketch streams for Jaccard similarity hashing, one finds the minimum element in each of $k$ permutation for comparison purposes, and then takes number_of_collisions / $k$ ...
152 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. ...
88 views

### Naming an algorithm after a copyrighted object

In machine learning, it is common to give algorithms quirky names. What happens if you think you've found a name that's actually quite fitting for an algorithm (catchy, descriptive, etc) -- but turns ...
55 views

### Problems and theories in CS that uses Fibonacci numbers

I want to know problems and theories where Fibonacci sequence is used and where we have some possibility to use Fibonacci numbers. I have found that- In counting number of steps for Euclidean ...
79 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 ...
278 views

### Hereditary substitution with a universe hierarchy

I've read about hereditary substitution for the Simple Lambda Calculus and for The Logical Framework with distinct terms and types. I'm wondering, are there any examples of hereditary substitution in ...
77 views

### Results in denotational semantics from model theory?

Denotational semantics interpret the theories of various lambda calculi in various (set-theoretic, domain-theoretic, category-theoretic, game...) models. Let $T$ be the theory of one such lambda ...
116 views

### Can two-tape read-only Turing machines recognize any recursive language?

Suppose that a $k$-tape read-only Turing machine receives its input on each $k$ tapes. It cannot write on the tapes, but it can move on them in both ways, even move off from the input. So for example, ...
123 views

### General Induction Principle

Let us suppose that we want to provide for each inductive type an axiom describing the associated elimination/induction principle. For example, given a definition for the naturals: ...
237 views

### Is DSPACE(n) = DSPACE(1.5n)?

From space-hierarchy theorem it is known that if $f$ is space-constructible then DSPACE($2f(n)$) is not equal to DSPACE($f(n))$. Here, by DSPACE($f(n))$ I mean the class of all problems that can ...
164 views

### Does Max Planar 3-SAT admit a PTAS?

Suppose we are given a formula $\phi$ of 3-SAT, with variables $x_1,\dots, x_n$ and clauses $C_1,\dots, C_m$. Consider the graph $G_\phi$ where there is one node for each clause $C_i$, for each ...
81 views

### Auction theory - Selling Multiple Items via Social Networks

I am trying to understand this paper. The one thing that I cannot wrap my head around is the payment policy for the Generalized Information Diffusion Mechanism. It is explained on page 72 with ...
699 views

### The TOC Blog Aggregator is Offline

I apologise if this is off-topic. It seems that the domain name has expired. I hope some member(s) of the community here (I am not one) may know who was the administrator/owner of that site. It was ...
### Why do most 0/1 matrices need linear arithmetic circuits of size $\Omega(n^2/\log(n))$?
I am reading Alon et al.'s paper Linear Circuits over $GF(2)$ and I am having trouble seeing the counting argument showing that most matrices need a circuit of size $\Omega(n^2/\log n)$. This result ...