All Questions

Filter by
Sorted by
Tagged with
2 votes
0 answers
65 views

An untyped lambda calculus for explicit memory management

I am trying to find resources on a lambda calculus one would use for explicit memory management, assuming there is such a calculus. The concept is as follows: one takes untyped lambda calculus, ...
Russoul's user avatar
  • 249
1 vote
0 answers
14 views

Fat-finger sequences: sequences of numbers as ids for items which are immune from repetition due to mistyping, etc

In real life I am a Software Quality Assurance Engineer who uses Jira to keep track of stories/bugs/issues, etc... On a given day I deal with hundreds of story/bug/etc ids. These ids are easy to ...
Rex Butler's user avatar
3 votes
0 answers
34 views

Complexity of minimizing the index of a subgroup of the free group

Let $\Sigma$ be a finite alphabet and $G$ the free group generated by $\Sigma$. Let $W$ be a finite subset of $G$. (Represented as a list of formal expressions of the form $a_1^{\pm 1}\ldots a_n^{\pm ...
Vanessa's user avatar
  • 2,181
4 votes
0 answers
188 views

Is Gnang's proof of Graceful Tree Conjecture correct?

Gallian's dynamic survey on graph labeling mentions Gnang's preprints which claim to resolve the graceful tree conjecture. The latest version of this preprint dates 2023 August. Another related ...
Cyriac Antony's user avatar
1 vote
1 answer
50 views

Hardness of the Metric TSP for the Maximum Metric

I know that it is not too difficult to construct a metric to show that the metric TSP is NP-hard. The typical example is (1,2)-TSP. I also know that Papadimitriou has shown that Euclidean TSP is NP-...
jfriemel's user avatar
1 vote
0 answers
33 views

Encoding of nodes in Binary Decision Diagrams

A straightforward implementation of Binary Decision Diagrams (BDDs) typically requires 24 bytes per node, with an additional 8 bytes commonly used for auxiliary data. Each node is encoded as a 4-tuple ...
Taylor Sasser's user avatar
0 votes
0 answers
20 views

On the Relationship Between Graph Isomorphism and Equivalence in ETL Workflow Dependency Graphs

Let $G = (V, E)$ and $G' = (V', E')$ be two DAGs representing dependency graphs of ETL workflows. Each node $v \in V$ (or $v' \in V'$) represents a task, which is a tuple $t_v = (q_v, d_v, s_v)$, ...
Zoom's user avatar
  • 1
0 votes
0 answers
28 views

A question on $m$ qubit

Let $\sigma$ be an $m$-qubit such that $Trace(\sigma^2)\le \frac{1+\epsilon^2}{2^m}$, then $D(\sigma , I/2^m)\le \epsilon$. Relevant Equations: $D(\sigma,\rho)=1/2 Trace(|\sigma-\rho|)$ where $\rho,\...
MathematicalPhysicist's user avatar
3 votes
1 answer
51 views

Quickest known integer relation algorithm in the case of signs

Let $x_1,\cdots,x_n,k$ be integers such that $|k|\le\sum_{i=1}^n|x_i|$. What is the quickest known algorithm to determine $w_i\in\{-1,0,1\}$ such that $k=\sum_{i=1}^nw_ix_i$ where they exist? What is ...
TheSimpliFire's user avatar
0 votes
0 answers
44 views

Is there a self-synchronizing binary coding like Fibonacci coding but ordered well when interepreted as std binary digits?

I'm investigating a possible self-synchronizing binary encoding for use in a variable length exponent floating point format like Posits. Posits use something like Elias Gamma encoding https://en....
Pierre Houston's user avatar
2 votes
1 answer
85 views

On the power of QMA(2)

I searched for references. But I could not find any. Is $EXP\subseteq QMA(2)$ known?
user72910's user avatar
0 votes
1 answer
101 views

Are there NPO (NP Optimization) problems that would require more than polynomial time even on a non-deterministic machine?

Consider an $\mathit{NPO}$ problem $O = (X,L,f,\mathit{opt})$ according to the definition of $\mathit{NPO}$ found in this answer. What I don't fully understand is what happens if we use a NDTM (non-...
SmartRock's user avatar
12 votes
1 answer
194 views

Computational complexity of the elementary theory of finite fields

Let $T_f$ denote the set of first-order sentences in the language of rings which are true in all the finite fields. That is, $T_f = \{\varphi \mid K \models \varphi, \text{ for every finite field } K\}...
Reijo Jaakkola's user avatar
1 vote
0 answers
87 views

Efficient algorithm to construct simple polygon from non-crossing orthogonal line segments

Given a set of $N$ non-crossing orthogonal (vertical and horizontal) line segments on the plane, is there an efficient algorithm to construct a simple orthogonal polygon that passes through all given ...
Mohammad Al-Turkistany's user avatar
-3 votes
1 answer
49 views

How do you get enough computing power to simulate a universe in a machine smaller than a universe? [closed]

I’ve watched on a TV show that you can fit all the information in the Observable Universe in a space smaller than the Observable Universe, but does this apply to the entire universe? I have an uneasy ...
someonewhohasasanota's user avatar
-1 votes
0 answers
73 views
+50

Is set cover with a fixed number of variables and an arbitrary number of constraints fixed parameter tractable?

I am an engineer who is working with some network optimization problem. After some investigation, I reallize that my problem has a form of a set cover problem but with some specific properties. $\...
Tuong Nguyen Minh's user avatar
1 vote
0 answers
50 views

Closed-form for exact number of iterations of binary search

(This is a cross-post from CS.SE). Consider a sorted list of $n$ elements $x_1, \ldots, x_n$. Using binary search to find $x_k$ in this list takes $f(n, k)$ iterations, where $f : \mathbb{N}^2 \to \...
Electro's user avatar
  • 111
1 vote
0 answers
140 views

Is finding the best permutation an NP-Complete problem?

We have a matrix $M$ of size $n$ by $n$ where $M[i][j] \ge 0$ and $M[i][i] = 0$. We want to create a permutation of integers $[1,\dots,N]$, like $\langle P_1, P_2,\dots,P_n \rangle$, such that $$ \...
Amir's user avatar
  • 544
3 votes
0 answers
63 views

Are there any programming languages based on the method of analytic tableaux, aside from Fitting's Proflog?

The method of analytic tableaux [0] describes a process by which logical formulae, particularly of first order logic, can be determined to be valid or invalid. From the Wikipedia entry: A tableau ...
jpt4's user avatar
  • 111
0 votes
0 answers
44 views

Why LOUDS is considered succinct coding?

LOUDS encoding is widely cited as succinct, e.g., in the papers, in Github repos, etc. It is straightforward that LOUDS takes 2n bits for encoding an ordered tree ...
Xavier Z's user avatar
  • 113
0 votes
1 answer
97 views

Deciding whether there are directed paths between two vertices of all possible lengths

I recently read a paper The presence of a zero in an integer linear recurrent sequence is NP-hard to decide by Blondel and Portier, in which they prove the statement The problem of determining for a ...
user918212's user avatar
1 vote
1 answer
95 views

The problem of approximating the diameter of a point set

given a set of n points P and a nxn matrix M such that for every two point u,v where M[u,v] is the distance between u and v , and the distance is pseudo metric, is there a property testing algorithem ...
adonis abboud's user avatar
1 vote
0 answers
55 views

Complexity of FirstMatch (Prefix Elimination) Operator for regular expressions

Consider the operator $\texttt{FirstMatch} : 2^{\Sigma^*} \to 2^{\Sigma^*}$ defined as follows: $$\texttt{FirstMatch}(L) = \left \{ y \mid y \in L, \forall \text{ prefixes } x \text{ of } y, x \not \...
Agnishom Chattopadhyay's user avatar
1 vote
1 answer
81 views

Is it possible to encode the structure of a binary cardinal tree with n nodes using only n bits?

By binary cardinal tree, I mean a tree with degree 2. The question confuses me because I know LOUDS/DFUDS can encode binary trees with 2n bits; however, this paper claims that it is possible to encode ...
Xavier Z's user avatar
  • 113
3 votes
0 answers
106 views

Why Huffman codes cannot be handled using matroid theory?

In Cormen's "Introduction to algorithms" it is stated that matroid theory cannot be applied to justify the greedy algorithm given for the construction of Huffman's codes. I was wondering ...
user1868607's user avatar
  • 1,049
0 votes
0 answers
14 views

What is a tight set for a face $F$ of the perfect matching polytope

I was reading the paper The Matching Problem in General Graphs is in Quasi-NC - Ola Svensson, Jakub Tarnawski. There the word mentioned in many places for example Definition 4.1 `$S$ is tight set for ...
Soham Chatterjee's user avatar
-4 votes
1 answer
174 views

How to pronounce HOAS?

I am not sure if this is on-topic, but I don't think I have any hope on any English learning website. HOAS refers to higher-order abstract syntax, which is a mechanism for representing bindings using ...
ice1000's user avatar
  • 957
0 votes
0 answers
33 views

Enhancing a bipartite perfect matching solution with 1-to-2 matchings

We're doing hobby events where people list their items followed by a wishlist of what they would like to receive in exchange for each one of their items, then the current algorithm finds the biggest ...
Juan Ignacio Suarez's user avatar
1 vote
0 answers
152 views

Transition from Mathematics to TCS [closed]

I am an undergraduate majoring in Mathematics and I am really interested in TCS. Most of the classes I have taken are pure math classes so I was wondering: what are the core TCS courses that I should ...
Frederico Oliveira's user avatar
1 vote
1 answer
84 views

Simple Coq simplification question

I am working through Software Foundations, I had a question about the leb_refl theorem from the induction chapter. Here is my solution: ...
whatisit's user avatar
0 votes
1 answer
122 views

Solution to Subset Sum Problem (in some sense) using Gaussian elimination modulo 2

Consider a set of natural numbers $S \in \mathbb{N}^n$ for some $n \in \mathbb{N}$. Assume that each number $s_i = S^T\cdot e_i$ meets $s_i \leq 2^m$ i.e. is written on at most $m$ number of digits, ...
C Marius's user avatar
  • 141
-2 votes
0 answers
58 views

What different computational powers do I get from an oracle for an undecidable problem?

Suppose that I have got an oracle to some undecidable decision problem, say, for some language $L$. Examples include Halting problem group isomorphism problem whether a Turing machine is a busy ...
shuhalo's user avatar
  • 1,159
0 votes
0 answers
53 views

Is there optimal or approximate solution to Single-machine scheduling problem with constraints?

I'm interested in particular setup of Single-machine scheduling. I'll use the Optimal job scheduling notation to specify the situation. I'm also aware of Interval scheduling. What I want to achieve is ...
Luxter's user avatar
  • 1
2 votes
2 answers
104 views

Weighted bipartite matching with no-cycle constraint

Given a weighted bipartite graph, I need to find a maximum-weight matching with the following additional constraint: the residual graph of the chosen matching is not allowed to contain any cycles. By ...
user168715's user avatar
4 votes
0 answers
114 views

Completeness, Compactness and LST in Type Theory

I'm just getting into model theory for type theory. I would like to know: How to properly define notions Compactness in type theory? Is There Completeness, Compactness and downward Löwenheim–Skolem ...
Ember Edison's user avatar
-1 votes
0 answers
27 views

Is it possible to verify membership of black-box models in a known hypothesis class?

In verification algorithms, the output is a binary decision (Yes/No). It was shown that those algorithms are highly efficient compared to classical algorithms where the decision has more information ...
ayaxxx's user avatar
  • 120
3 votes
2 answers
118 views

How to prove that $\exists A. ~ A \times (A\to F~ A)$ encodes the greatest fixpoint of $F$?

Following Wadler's paper "Recursive types for free" and having spent some months on reconstructing the proof that $\exists A. ~ A \times (A\to F~ A)$ is the terminal $F$-coalgebra, I am ...
winitzki's user avatar
  • 542
4 votes
0 answers
76 views

Is the encoding of existential types in System F adequate?

This is somewhat related to How to encode a function from an existential type Existential types can be encoded in System F. If $P$ is any type constructor, not necessarily covariant, then the ...
winitzki's user avatar
  • 542
-2 votes
0 answers
37 views

What is TMSAS-Enumerator?

Actually, I know what is meant by enumerator according to Turing Machine topics in Automata but there are multiple observations about TMSAS. Here enumerator with context to automata and Turing ...
Supravo Biswas's user avatar
5 votes
0 answers
75 views

A split-consistency property of a formal language

I am looking for occurrences in literature of the following property of a formal language $\mathcal L$ over an alphabet $\Sigma$ For any quadruple of words $a,b,c,d\in\Sigma^*$, if $ac,bc,ad\in\...
Gejza Jenča's user avatar
1 vote
1 answer
148 views

Can the Sigma type be defined in terms of the pi type in dependent type theory?

Using the Curry-Howard Correspondence and the fact we can write: $$\forall x: f(x) \equiv \not \exists x: \lnot f(x)$$ Can we write the $\sum$ type in terms of the $\prod$ type? $$\sum(x:A)B(x) \...
zooby's user avatar
  • 113
3 votes
0 answers
85 views

How to prove that a problem is not smoothed-polynomial?

Many research works use Smoothed analysis to prove that some NP-hard problems can actually be solved efficiently in typical cases. A different notion with a similar goal is Generic-case complexity. ...
Erel Segal-Halevi's user avatar
0 votes
0 answers
66 views

Challenges and Optimization Techniques for Translating Pratt's Certificates to CNF

I am investigating Pratt's result that Primality is in NP. This means that for a given natural number input X, there exists a CNF that is satisfiable if and only if X is a prime number. I am trying to ...
Jogenara's user avatar
  • 121
1 vote
1 answer
119 views

Where does a problem lie which is NP-hard but not QMA-hard?

I saw this complexity classes diagram in this quantum computing paper in NATURE. Based on the standard assumption of $P\neq NP\neq QMA$, they also seem to have related the NP-hard and QMA-hard ...
Manish Kumar's user avatar
0 votes
0 answers
73 views

Evidence extended GCD is in $TC^0$

Despite centuries of search extended $GCD$ is known to accommodate one algorithm which is the Euclidean algorithm (the solution through Integer Linear Programming which needs basis reduction goes ...
Turbo's user avatar
  • 13k
0 votes
0 answers
50 views

Does randomness help depth?

Suppose we have a $RNC^i$ or $BPNC^i$ algorithm for a problem, is it suspected that the problem has an $NC^i$ algorithm or just an $NC^j$ algorithm for some $j\geq i$? Is there any evidence for ...
Turbo's user avatar
  • 13k
0 votes
0 answers
25 views

Efficient PTAS for 2 identical knapsacks?

Input: $v_1,v_2,...,v_n$ item profits, $0<w_1,w_2,...,w_n\leq1$ item weights. Output: $B_1,B_2$ which are subsets of $\{1,2,...,n\}$ s.t. they are disjoint, and such that $\forall i\in\{1,2\}:\sum_{...
alon's user avatar
  • 1
0 votes
0 answers
64 views

Is a problem, that is $L$-complete under non-uniform $AC^0$ reductions, necessarily outside of (non-uniform or uniform) $NC^1$?

I don't have much intuition about non-uniformity so the question may be quite naive.
A. G.'s user avatar
  • 43
0 votes
0 answers
74 views

Bellman-Ford with infinite weights

I have a graph with weights of the form $a \omega + b$ where $a,b \in \mathbb{Q}$ and $ \omega$ is an infinite value, that is, a value such that for any rational number $q$, $q \le \omega$. The ...
user1868607's user avatar
  • 1,049
4 votes
1 answer
100 views

Smoothed analysis in the Turing machine model

Smoothed analysis is usually defined using real numbers: given $n$ and $\sigma$, the smoothed runtime of an algorithm is the maximum, over all inputs of size $n$, of the runtime on the input when it ...
Erel Segal-Halevi's user avatar

15 30 50 per page
1
2 3 4 5
260