All Questions

Filter by
Sorted by
Tagged with
0
votes
0answers
3 views

complexity class of a function - linear combinations and reductions (Fermionant, immanant, $GL_n$ representations)

The fermionant is a matrix function from physics, which is indexed by a positive integer $k$: \begin{align} \operatorname{Ferm}_k(A) = \sum_{\lambda} d_{\lambda}^{(k)} \operatorname{Imm}_{\lambda^T}(A)...
0
votes
1answer
18 views

Property testable in sublinear time in bounded degree graphs but not in general graphs

Is there some natural property that is testable in strongly sublinear time (i.e. $O(n^{1-\epsilon})$ for some $\epsilon > 0$) in bounded-degree graphs but not in general graphs? If not such ...
0
votes
0answers
35 views

A Simpler Solution for a special case of the Set Cover problem

We decomposed a simple polygon into many small regions. Then we estimated a visibility polygon of a point by a subset of the small regions. Now I need the minimum set of visibility polygons that can ...
0
votes
0answers
14 views

How do we evalute the difference between a predicted value $\hat{v}$ and the true nash equlibrium value $v$

Consider a bimatrix game problem with matrix $A$ and $B$. Suppose we have a prediction value $\hat{v}$ for the Nash equilibrium value $v$. However, we do not have the strategy profile behind this ...
-5
votes
0answers
35 views

If $A\leq_p B$ and $B$ is NP-Complete, is $A$ in NP? [closed]

Let $A\leq_P B$ mean that the language $A$ is polynomial time reducible to $B$. It is a theorem that $A\leq_P B$ and $B\in \text{P}$ then $A\in \text{P}$. My question is, if $A\leq_P B$ and $B\in \...
-2
votes
0answers
21 views

Geometric Intersection Graphs Online Coloring

My master's degree thesis is about geometric intersection graphs online coloring, unfortunately, I have so much doubt when I read papers on this subject and many of the results were incomprehensible ...
0
votes
1answer
45 views

Can finite difference methods approximate the space/time complexity of given programs?

While benchmarking a language prototype, I realized that I had a superlinear implementation of a test program, but wasn't sure if it was quadratic or cubic. I stayed up too late and wrote half a page ...
-2
votes
0answers
54 views

A Query regarding Polynomial hierarchy collapse to a finite level (level 2)

Assuming a hypothetical scenario that complexity class $PSPACE$ is shown to belong to complexity class $NP^{coNP}$ the Polynomial Hirerchy Collapses to a finite level. If I am correct, above result ...
1
vote
1answer
166 views

Is this a novel technique for determining whether or not two rotated rectangles collide?

I was trying to determine whether or not two rectangles rotated around their centers were colliding and randomly thought to try the following algorithm: Rotate both rectangles by the negative rotation ...
-3
votes
1answer
123 views

Logic of counting elements of the domain [closed]

I need to describe a logic of counting elements of the domain: in each model, the function outputs the number of elements in the domain of the model. What kind of function(s) shall be in the signature?...
0
votes
0answers
116 views

I think I may have discovered a new algorithm for a common problem. Now what?

I was trying to solve a common problem the other week and upon checking Stackoverflow there was a solution, but it just seemed like there should be a better way to do it. I thought about it for a ...
8
votes
1answer
170 views

Does Horn SAT (Horn formula in CNF) have an integral polytope?

In some ways, my question is related to this: Is the matching polytope integral? Matching and Horn-SAT are both polynomial time solvable.. So I wonder if there is a Horn polytope, similar to the ...
0
votes
1answer
89 views

Complexity for universal Counter Machine with {0,1}-valued registers

Consider a universal $\{0,1\}$-$k$-counter machine where each of the $k$ registers has a value in $\{0,1\}$ (as opposed to any non-negative integer in the usual formulation), and there are states $q_1,...
-3
votes
0answers
50 views

do you know any paradoxes on information theory? [closed]

is there any interesting paradox about entropy?
1
vote
0answers
22 views

Reference showing global optimality of local minima for matrix factorization

Consider the following matrix factorization problem: Given an $n\times m$ matrix M, find $n\times r$ and $m\times r$ matrices $U$ and $V$ such that $||UV^T - M||_F^2$ is minimized. I have heard it ...
-3
votes
0answers
21 views

Prove that $\text{QSAT}_2$ is complete in $\Sigma_2$ under polynomial mapping reductions [closed]

We define $\text{QSAT}_2$ to be the set of all true statements of the form $$ \exists x_1, x_2, \dots, x_k \forall x_{k+1}, \dots, x_n \ \ \phi(x_1, \dots, x_n), $$ where $\phi$ is a CNF on the ...
-1
votes
0answers
64 views

Open Problems in Quantum Complexity Theory (2021)

What are some open problems in quantum computing or complexity theory where a novice researcher could reasonably hope to make contributions with a few months of steady effort? I know this question has ...
0
votes
0answers
66 views

Useful primitives CPUs could provide, from TC0 (or NC1)

I just listened to XYZ talking about "How Universal Is the Idea of Numbers?", and bashing the concept as an accidental historical artifact. He suggested that totally different computational ...
1
vote
0answers
35 views

Is there a measure of string distance which remains small between two strings after encryption?

I have a theoretical problem inspired by a real world problem I have come across. I am writing code for some spreadsheets, and part of the process is error correcting names with typos. One ...
-1
votes
0answers
55 views

Are total recursive functions efficiently invertable?

I'm doing some work with cryptographic primitives that act on arithmetic circuits. We found a result from a few years ago that would suffice for our purposes, but it assumes the functions in question ...
-2
votes
2answers
131 views

Partition a graph into two clusters

Suppose given a complete weighted graph $G=(V,E)$, with positive weight. Are there an algorithm that partition $G$ into two clusters $C_1,C_2$ such that sum of heaviest edges in $C_1,C_2$ minimized? ...
0
votes
0answers
34 views

Recursive Bijections Between Countably Infinite Sets [closed]

The textbook I am currently studying (Introduction to Kolmogorov Complexity and Its Applications by Li and Vitanyi) uses the term 'recursive bijection'. In this context I believe that recursive refers ...
2
votes
1answer
129 views

Does a finite, polynomially-bounded CFG translate into a polynomially-bounded DFA?

We are given a family of context-free grammars $\{ G_1, G_2, G_3, ..., G_n, ...\}$ where each $G_n$ generates strings only of length $n$ and obeys other constraints specified below. We want to study ...
5
votes
1answer
206 views

Computational complexity of Turán-type problems

According to Turán's theorem (with $r=n/2$), any graph $G$ with $n$ vertices and at least $n(n-2)/2$ edges must contain a clique of size $n/2+1$. My question is: how hard is it to find this clique?$^*$...
4
votes
0answers
45 views

Coinduction principle for smash products of pointed cpos

In "Relational Properties of Domains", Pitts gives a coinduction principle for pointed cpos (cppos). In corollary 6.13 (below), he specializes it to cppos constructed as fixed points of cppo-...
2
votes
1answer
141 views

3SAT to 1-in-3SAT reduction with additonal constraints

The simplest Reduction for 3-SAT to 1-in-3-SAT reduction is as follows: For each 3SAT clause: $x+y+z=1$ Introduce 4 new variables $\{a, b, c, d\}$ and replace original clause with below 3 clauses: $R(...
1
vote
0answers
81 views

How typical are odd-H-minor free graphs?

Can anything be said about how typical are odd-H-minor free graphs? (definition of odd-minor-free is in Section 2.2 of notes, page 20 of slides). For instance, for a random graph with $n$ vertices, $...
-2
votes
0answers
94 views

Looking for proof that the integrality gap is a lower bound on the approximation ratio [closed]

I am trying to understand why the integrality gap is a lower bound on the approximation ratio. I have read the threads about the integrality gap and the approximation ratio in this forum, but I would ...
-1
votes
0answers
47 views

Universally agreed upon parser types?

I'm currently studying the theory of compiler design and I bumped into a bit of a hurdle with parsers, basically, I don't fully get what the general consensus is on the types of parsers there is, a ...
0
votes
0answers
16 views

Fast filter for concurrent version vectors (vector clocks, lamport clocks) from a set

I have a set of version vectors (or vector clocks) and need to implement a filter function that takes this set and returns a new set where all elements are either "equal", "happened ...
1
vote
0answers
59 views

Smallest nonzero eigenvalue of a sum of +1/-1 rank-one matrices?

Suppose we have a $k\times k$ matrix $A = \sum_{i=1}^{n} a_i a_i^T$ where $n \leq \mathrm{poly}(k)$ and each $a_i\in\{-1,1\}^{k}$. It is easy to prove that the largest eigenvalue of $A$ is at most $\...
0
votes
0answers
97 views

Does this sum-product algorithm make more sense?

Recall the belief propagation "sum-product" algorithm (from wikipedia): $\forall x_v\in Dom(v),\;$ $\mu_{v \to a} (x_v) = \prod_{a^* \in N(v)\setminus\{a\} } \mu_{a^* \to v} (x_v)$ $ \mu_{...
0
votes
0answers
42 views

Functor Image example in Roman’s CT book

In his book, An Introduction to the Language of Category Theory,Steven Roman provide us with the following diagram: Then, he states: Note that in this example, the object part of F is not injective, ...
0
votes
0answers
74 views

Is there some n such that lambda calculus with only n variables is Turing-complete?

Typically in lambda calculus you have an infinite stock of variables. Could we get away with a finite set?
0
votes
0answers
128 views

Is this "choose and switch" game just 2SAT in disguise?

Suppose you have $n$ switches lined up on a wall, labeled left to right from $1$ to $n$. The switches are either on or off. You get a list of $q$ choices that must be made. A choice consist of two ...
2
votes
2answers
216 views

Some issues with proof of Fundamental Theorem of Statistical learning

I am reading the book "Understanding Machine Learning" by Shai Shalev-Shwartz and Shai Ben-David. The theorem 6.7 has several equivalent statements for a class of functions $H$. The first ...
0
votes
0answers
21 views

Going from one base packing to another using basis exchanges

Suppose I have a matroid $M = (E, \mathcal{I})$. It is a known fact that given any two bases $X_0$ and $X_n$, we can transform $X_0$ into $X_n$ by repeatedly applying the basis exchange axiom. So ...
-1
votes
0answers
50 views

What kind of background do I need to study the game of sprouts?

Sprouts is a paper-and-pencil game invented by the late John Conway (also known for having invented the Game of Life, in addition to his many contributions to a number of fields of math) and Mike ...
-2
votes
0answers
26 views

Encoding of Constraints in Reductions (like in k-MAX Problems)

The general question is how to encode constraints in reductions to problems that do not have such constraints. More specifically, there is a straightforward reduction from SetCover to VertexCover. But ...
0
votes
1answer
89 views

Finding top-K items in a sliding window

Imagine we have a stream of bank transactions. Each transaction has a target account and some amount of money. I'd like to find top K accounts over some period of time (e.g. last 7 days) which ...
2
votes
2answers
107 views

Information and Coding Theory Texts

I am coming from a pure mathematics (in analysis) background and am curious to learn some information and coding theory. I am after some recommendations on texts. Due to my personal background I am ...
3
votes
1answer
70 views

Recursive generic oracles

In Fenner, Stephen; Fortnow, Lance; Kurtz, Stuart A.; Li, Lide, An oracle builder’s toolkit, Inf. Comput. 182, No. 2, 95-136 (2003). ZBL1025.68041, the authors go through a variety of generic oracles. ...
5
votes
5answers
274 views

Relationship between Random Graph Theory and TCS

Sorry for this large and vague question. I am a new grad probability student recently interested in random graph theory(RG). I heard from someone in math department that RG has close relationship to ...
0
votes
1answer
26 views

Are perceptual hashes connected to audio/video compression?

Without loss of generality, I'll only talk about video, but this should apply to any sort of signal. A perceptual hash function (WP) maps videos to fingerprints such that each fingerprint's preimage ...
0
votes
1answer
119 views

What is a known sequence for which being constant is not provable?

My question concerns the property of being constant for computable functions ${\mathbb N}\to \{0,1\}$, within any common framework $T$ strong enough to include Heyting arithmetic (and of course not ...
1
vote
0answers
75 views

Input length and calculation time to simulate a quantum measurement

Let us consider $n$ quits $b_i$. Let us start from the state $|0,0,...,0>$ and apply a circuit $C$ composed by $m$ quantum gates, with $m$ polynomial in $n$. The final state is $C|0,0,...,0>$. ...
1
vote
1answer
99 views

Lower bound for proving a random 3-SAT formula is unsat?

For a random 3-CNF formula with n variables and m clauses, assume this formula is unsat, what is the lower bound for proving it to be unsat? Some results posted in Lower bounds for random 3-SAT via ...
-2
votes
0answers
26 views

Modular decomposition calculator

I am trying to find an easy to use modular decomposition (MD) calculator, possibly online. It is just to make some tests on (small) comparability graphs to decide if it is worthy to use MD as part of ...
0
votes
0answers
92 views

Is polynomial-time the same in all classical computational models?

There are many models of computability, all giving the same notion of 'computable function'. To pick a few examples: Turing machines (with variants: one-ended, two-ended, multiple tapes...) RAM ...
1
vote
1answer
72 views

Are coproduct types redundant in presence of natural numbers and $\Sigma$-types?

In the homotopy type theory book section A.2.5 defines $\Sigma$-types, A.2.6 coproduct types and A.2.9 the natural numbers type. If we already have $\Sigma$-types and the natural numbers type can we ...

15 30 50 per page
1
2 3 4 5
230