# All Questions

13 views

### Is it enough to sort for polynomially many 0-1 sequences for a sorting network?

The 0-1 principle says that if a sorting network works for all 0-1 sequences, then it works for any set of numbers. Is there an $S\subset \{0,1\}^n$ such that if a network sorts every 0-1 sequence ...
54 views

### Why was there a need for Martin-Löf to create intuitionistic type theory?

I've been reading up on Intuitionistic Type Theory (ITT) and it does make sense. But what I'm struggling to understand is "why" was it created in the first place? Intuitionistic Logic (IL) and ...
28 views

### An algorithm to produce, not necessarily efficiently, another algorithm that efficiently solves the Rubik cube

How complex is the task to formulate an algorithm that produces, not necessarily efficiently, another algorithm to efficiently solves the Rubik cube? Has it been attempted before? What is the latest ...
25 views

### Software that generates and solves a Lasserre hierarchy

Suppose L is a linear program that is a relaxation of some 0/1 integer linear program ILP. There is a systematic way to construct SDP relaxations of ILP that are tighter than L by using a Lasserre ...
43 views

### Techniques introduced to log-rank conjecture

What have been some of techniques (like discrepancy, arithmetic combinatorics) that have been introduced to shed light on Log-rank conjecture which roughly states that deterministic communication ...
22 views

### Maximum set cover of graph with r density requirement

I am trying to implement a satisfactory solution to a variation of maximum coverage problem. A set of people is in relation to a set of channels by liking them. Each channel has a unique relationship ...
115 views

### Partition of a set of integers into subsets with prescribed sums

I saw this problem: A non increasing sequence of positive integers $m_1,m_2,..., m_k$ is said to be n-realizable if the set $I_n=\{1,2,..., n\}$ can be partitioned into $k$ mutually disjoint subsets ...
57 views

### Decidability of CFG ambiguity

I have been trying to show the following language is undecidable. $L = \{ (\langle G \rangle , n ): G$ is a context-free grammar with an ambiguous string of length $\le n \}$. I think it is ...
21 views

### Quantum multi valued decision diagrams [migrated]

I recently came across the paper "QMDD: A Decision Diagram Structure for Reversible and Quantum Circuits" by Thornton and Miller. It deals with a way of compactly representing transformation matrix ...
73 views

### Proof of Non Deterministic Space Hierarchy Theorem [on hold]

I am trying to prove the Non Deterministc Space Hierarchy Theorem, which says: If $f$ and $g$ are two functions such that $f=o(g)$ where $g$ is fully space constructible and $g(n) \ge \text {log }n$, ...
51 views

### A bucket must exist before anything can be put into it. What does not have to? [on hold]

Going over the Wikipedia for Bucket (computing), I have noticed under the section 'Features of a bucket' it mentions: A bucket must exist before anything can be put into it. Why was it so ...
1k views

### Problems with big open complexity gaps

This question is about problems for which there is a big open complexity gap between known lower bound and upper bound, but not because of open problems on complexity classes themselves. To be more ...
20 views

### multiobjective optimization is easier with fewer objectives, right?

i guess that optimization on nonconvex problems can usually reach better results when there's fewer criteria in the objective function. for example, in a given amount of search time, ten equally ...
27 views

### I dont understand the reduction of 3DM to Partition Problem [on hold]

I am real need for understanding the reduction from 3DM to Partition problem. I am following the textbook by Gary and Johnson. I am not understanding the argument which says that, If its 3DM will have ...
41 views

### Looking for easy applications of fractional cascading

I want to give a couple of talks on fractional cascading, one of which will focus on applications. I'm looking for applications that make use of the full version of fractional cascading, not just the ...
97 views

### Why can't Horn-SAT be solved in Log-space? [on hold]

A simple algorithm for Horn-SAT (in CNF) is the following: Given: A Horn formula $\phi$ in CNF. Find a unit clause (a clause with one literal) $C_i$. $~$Set the variable $x_j$ appearing in $C_i$ to ...
115 views

### Efficient recalculation of the maximum flow when edge capacities are reduced

Assume that we have a (directed) graph $G(V \cup \{s, t\}, E)$ and an (integer) capacity function $c : E \mapsto \mathbb{N}$. Let $f : E \mapsto \mathbb{N}$ be a maximum $s-t$ flow on this graph. ...
43 views

### Karatsuba's algorithm smart step analysis [on hold]

I have a problem that I want to solve. I really tried but it does not budge. If the input is of size n for Karatsuba's algorithm We have three steps in Karatsuba's algorithm: 1) Recursively compute ...
88 views

### Good algorithms to solve ATSP

What are some good neighborhood-based local search algorithms or strategies to solve the Asymmetric TSP ? I see many 2-OPT and K-opt based algorithms (e.g. Lin-Kernighan implementations), but I think ...
68 views

### Minimum order of partite in a bipartite graph

I want to create a bipartite graph where the first partite $U$ contains $L$ vertices with degree $k$ and the second partite $V$ contains $N$ other vertices with degree $a$. I need to find the minimum ...
83 views

### Upper bounds on higher order eigenvalues of regular graphs

Suppose $G$ is an undirected $d$-regular $n$-vertex graph for some constant $d$. Let $\lambda_k$ be the $k$-th largest eigenvalue of the normalized laplacian $L$ of $G$ (defined as $I - \frac{1}{d} A$ ...
60 views

### Many-one reduction from inequality problem to equality problem

Let the k-inequality-MIS problem be the decision problem whether an arbitrary graph $G=(V, E)$ contains a maximal independent set of at least size $k$, that is the corresponding language is: ...
61 views

### All NP-Problems have pseudopolynominaltime algorithms [closed]

Knapsack is weakly Np-complete. Every problem in NP is in polynominal time reduceable to an Knapsack instance. Knapsack has a pseudopolynominaltime algorithmvia dynamic programming. So there is a ...
68 views

### Finding Contextual Nodes in a Knowledge Graph

I'm currently participating in developing a knowledge graph that uses ConceptNet and a few others as its data sources. It uses the same architecture as ConceptNet namely it is stored as a Hypergraph ...
69 views

### Comparing the Kolmogorov complexity of theories - Part 2

Chaitin's incompleteness theorem says no sufficiently strong theory of arithmetic can prove $K(x) > L$ where $K(x)$ is the Kolmogorov complexity of natural number $x$ and $L$ is a sufficiently ...
497 views

### Is there an oracle such that SAT is not infinitely often in sub-exponential time?

Define $io$-$SUBEXP$ to be the class of languages $L$ such that there is a language $L' \in \cap_{\varepsilon > 0} TIME(2^{n^{\varepsilon}})$ and for infinitely many $n$, $L$ and $L'$ agree on all ...
48 views

### Finite state transducer with infinitary outputs or without emphasis on acceptance?

1) Is there a notion of (deterministic) finite state transducer (FST) that allows the possibility of producing an infinite stream of output symbols? In other words, one where the transduction ...
30 views

### Pseudoflow in oriented graph

I have a hard time solving the following problem: We have an oriented graph with positive integer capacities. We are also given for each vertex v the minimal sum of flows from edges in in-direction ...
158 views

### Has this formulation of pursuit evasion been researched? Similar to Helicopter Cops and Robbers Game

There are pursuers and evaders in the vertices of a directed graph G with one component. Each vertex must have atleast one outgoing edge (can be a loop). At each time t: The evaders must move ...
204 views

### Are there any interesting open questions having to do with submodularity, specially in the intersection of theoretical machine learning?

I was interested in knowing about open research topics related with sub modularity, specially within its intersection with theoretical machine learning (and related topics). I am particularly ...
33 views

### Detect highly weighted but also densely inter-connected subnetworks

In a connected / undirected / node weighted (with both positive and negative weights) network, there are many papers studied about the 'Maximum weight connected subgraph' problem. But are there any ...
54 views

### non-Hamiltonian cubic planar graphs [on hold]

What is the current state of knowledge about whether a polynomial deterministic algorithm has to be able to output every Hamiltonian circuit in every instance of a cubic planar graph $G$ in order to ...
67 views

### Complexity of Approximating Vandermonde Determinant

Given an $n\times n$ Vandermonde integer matrix with structured integers (such as arithmetic or geometric progression). Is complexity of approximately computing Vandermonde determinant upto ...
55 views