All Questions

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

Can equations be used to transmit large amounts of information instead of directly sending it?

Can equations be used to send large amounts of information rather than sending the information itself you send an equation that when solved reveals the information? So rather than downloading billions ...
0
votes
0answers
28 views

Is there a term for 'no-turn-back walk' in graph theory?

Let $G$ be a finite undirected graph. A walk in $G$ is a finite sequence $<v_1,e_1,v_2,e_2,\dots,v_{k-1},e_{k-1},v_k>$ where $v_j$'s are vertices in $G$, $e_j$'s are edges in $G$, and $e_j=v_jv_{...
-1
votes
0answers
25 views

Existence of a Wide Path

Say I have a tournament graph $G = (V, E)$ where every edge has a unique positive weight, and I have a function $f: V \rightarrow V$ with the following property: For all $x \in V$ then $(x, f(x)) \in ...
-2
votes
0answers
40 views

Expert Opinion on the Importance of Polynomial Hierarchy Collapse

$P\ vs\ NP$ and $NP\ vs\ co-NP$ are perhaps the two central questions in TCS and Complexity Theory with numerous surveys devoted to these problems. But (relatively) not much has been discussed ...
2
votes
0answers
29 views

Approximate (in hamming distance) subset representation

Let us have a set $S$ and a subset $T \subseteq S$. I want to find an approximate representation of $T$, i.e. I want to represent (exactly) a set $T'$ that is close to $T$. That is, I want the ...
1
vote
0answers
19 views

Does high connectivity of line graph of $G$ imply high (cyclic) connectivity of $G$?

All graph considered here are finite, simple and undirected. We know that a graph $G$ is $k$-edge connected if and only if its line graph is $k$-connected (where $k\in\mathbb{N}$). In particular, if $...
0
votes
0answers
23 views

Is having a particular form equivalent to being computable for functions on Church numerals?

In SKI-combinator calculus, consider the following function which reduces an expression (involving SKI and variables) to a canonical form: ...
-2
votes
0answers
32 views

Polynomial time delay and Amortized analysis

In order to estimate the complexity of output sensitive algorithm, we usually use Polynomial time delay or Amortized analysis. Then how to select the analysis methods, why we don't only use Amortized ...
2
votes
0answers
61 views

Online *detailed* tutorials about Komogorov Complexity

I'm a private math tutor who also tutors some theoretical CS. Last semester I had a student who needed tutoring in Kolmogorov Complexity. I told her that I only know about Kolmogorov Complexity, but ...
2
votes
0answers
45 views

Comparative communication complexity?

I was reading the book "Communication Complexity" by Kuschilevitz and Nisan and in Exercise 1.18 they introduce a variant of the normal vanilla 2-person deterministic communication ...
5
votes
1answer
114 views

Reference for automatically deriving dynamic programming algorithms from recursive algorithms?

This is what I'm looking for. Take a recursive algorithm: def fib(n): if n == 0 or n == 1: return n else: return fib(n-1) + fib(n-2) and turn it into ...
1
vote
0answers
33 views

Is the following special case of multiway number partitioning NP-hard?

The following problem is a decision problem of multiway number partitioning (wikipedia) (Note that $k$ is also a part of an input in the following problem, while $k$ is a fixed number in wikipedia ...
3
votes
0answers
37 views

Circuit uniformities more restrictive than $DLOGTIME$

$DLOGTIME$-uniformity was introduced by Barrington et al. here, and seems to be the standard lowest uniformity measure used for e.g. constant-depth circuit classes ($AC^0$, $ACC^0$, etc.). Are there ...
-2
votes
0answers
35 views

Is it possible to find closest number to a given irrational one, which is obtained by dividing 2 numbers in a given range faster than O(n^2)?

Let's say I have a range from 11 to 99 I need to find: abs(a/b)-k = min, a nd b - integer, k-an irrational number I can just look at all pairs of numbers in ...
1
vote
0answers
31 views

What type of Problems (Class and types) Can Be Solved Effectively with Quantum Computers?

The Question: I'm trying to understand the type of problems that Quantum Computers are/will be good at solving and if there is a special class to categorizes these types of problems (e.g. Do we ...
-2
votes
0answers
29 views

How to apporach the DFA/NFA Formation of 6 characters of length [closed]

I want to make a DFA of a language that should be atleast 6 characters having at least one small letter, atleast one capital letter as well as atleast one numerical digit . The issue is I am not able ...
2
votes
0answers
45 views

Summing over weighted paths optimally

Given an edge-weighted directed graph, how do you sum over all weighted paths between A and B while using the smallest number of multiplications? Is there a name for this problem? This comes up in ...
8
votes
3answers
440 views

What's the logical counterpart to jumps with arguments on CPS terms?

It's well known that the CPS (continuation-passing style) translation often employed in compilers corresponds to double negation translation under the Curry-Howard isomorphism. Though often the target ...
5
votes
0answers
75 views

For which type systems have normalizaton proofs been formalized?

I am trying to understand what the open problems are in the area of formalizing proofs of normalization for type systems. Obviously STLC has been done many times. For predicative System F, I found one ...
3
votes
1answer
132 views

Proof and interpretation of the No Free Lunch theorem in data privacy

This question relates to a supposed counterexample to the No Free Lunch theorem governing data privacy mechanisms, as stated by Kifer et al (Section 2.1). Colloquially, the theorem states that no ...
3
votes
0answers
51 views

Expressive power of lambda-calculus with restricted application

Consider a syntactic restriction of the (untyped) $\lambda$-calculus in which an application cannot have another application as an immediate subterm. More precisely, restricted terms ($R,S,...$) and ...
2
votes
1answer
66 views

On cubic planar graphs with face boundaries of length divisible by 4

All graphs considered here are finite, simple and undirected. Let $\mathscr{G}$ denote the class of cubic plane graphs for which all face boundaries are of length divisible by four. The 3-cube $Q_3$ ...
-4
votes
0answers
34 views

Abstract Interpretation [closed]

I need some help with this exercise, I have been struggling a long time to manage it, can someone please help me with how to solve it?
0
votes
0answers
74 views

Computational complexity of Private Computation

In a recent work (Sun2017), Sun and Jafar defined the Private Computation (PC) problem where a user wants to compute a function of $K$ datasets, using $N$ distributed and non-colluding servers, ...
-1
votes
0answers
34 views

Semantics of assert b before S - Nielsen and Nielsen Exercise 3.2

I was wondering how to express this statement in natural and structural operational semantics. Further, how would we define the statement 'assert b' only.
4
votes
0answers
106 views

Split a string of positive numbers into substrings with decreasing totals

Suppose we're given a string of $n$ positive numbers and asked to split it into the maximum number of substrings whose totals are decreasing. I have an $O(n)$ time DP algorithm, but is it already ...
2
votes
0answers
78 views

Subtle part of seeing $C(F) \geq \chi(f)$

This question is certainly below research level, however I figured I would get the best answer here. I just started learning about computational complexity (from Arora and Barak) and I have a ...
0
votes
0answers
40 views

Which is more expensive, structural or nominal type-checking?

A type system is nominal when types can be given new names, and those new names are attached to new behaviors. To me, type-checking programs in a nominal type system seems like it must be no less work ...
-1
votes
0answers
54 views

Why query complexity is said to lower bound time complexity?

Generally, query complexity is thought of as a lower bound on time complexity. It might be true if data is read sequentially. However, in quantum computation, state preparation routines exist that ...
1
vote
0answers
22 views

How to deal with the time to minimize a function in a given interval?

I'm writing a paper in which I designed an algorithm running in $O(n^2m)\cdot T(f)$ to solve my problem, where $n,m$ is the size of input and $f:\mathbb{R}\rightarrow \mathbb{R}$ is a function, and $T(...
-1
votes
0answers
41 views

Equivalence of XML queries

$\textbf{Problem statement:}$ Given a set of tree patterns $\{P,P_1,...,P_k\}$ where each $P_i$ has the same topology as $P$ (i.e. $P_i$ and $P$ have the same sets of nodes and edges excepting the ...
0
votes
0answers
32 views

Using error-correcting codes in multi-player games

There is a connection between any two from error-correcting codes, interactive schemes, and PCP. For quantum works, I found papers such as JV15 & Ji15. And there are classical examples about 20 ...
-1
votes
0answers
164 views

The Riemann Hypothesis as an halting problem

Matiyasevich has reformulated RH as a computer science problem : "a particular explicitly presented register machine with 29 registers and 130 instructions never halts", see this reference . ...
9
votes
2answers
756 views

Randomized algorithms not based on Schwartz-Zippel

Are there any problems that are known to be in a randomized complexity class (e.g. RNC, ZPP, RP, BPP, or even PP), but not in any lower non-randomized class (e.g. NC, P, NP), and whose membership in ...
19
votes
1answer
803 views

FOCS virtual fee $600

I'm not sure this is on topic here, but probably can be best answered by this community, so I'm posting it as a soft-question. Due to the pandemic, FOCS 2021 will be a virtual conference. Most ...
1
vote
0answers
39 views

Cycle double covers of cubic graphs using only a few cycles

This is a reference request question. Let $G$ be an arbitrary cubic graph. Is the problem of finding a cycle double cover $D$ of $G$ with minimum number of cycles in $D$ studied in the literature? I ...
1
vote
1answer
162 views

2-Center problem with forbidden pairs

Is there a nearly linear-time 2-approximation (or $O(1)$-approximation) algorithm for the following problem? 2-Center with Forbidden Pairs input: Bipartite graph $G=(V,E)$ where each vertex $v$ is a ...
1
vote
1answer
160 views

How to show that Color Tiles is NP-Complete

Color Tiles is a puzzle game where color tiles are laid out in a rectangular grid. A tile is visible to an empty grid cells if there is a clear line-of-sight in one of the 4 cardinal directions (You ...
0
votes
0answers
58 views

A fundamental question about the proof by induction in session types

I have a question about proof by induction in the domain of session types. Let's assume we have the following lemma: $$ \text{Let}~ \Gamma \vdash P : T. ~~\text{If } P = \mu X. Q ~~\text{then}~~ \...
0
votes
0answers
18 views

How does symmetric difference of b-matchings look like?

It is easy to see that symmetric difference of two matchings are cycles or simple paths. But what about b-matchings? Is there anything known about how they look? Even for restricted cases such as ...
1
vote
0answers
26 views

Cycle decompositions of locally linear 4-regular graphs

(Preface) We consider only finite, simple, undirected graphs here. An orientation of a graph $G$ is obtained by assigning some direction to each edge of $G$. (Question starts) A graph is locally ...
-1
votes
0answers
38 views

How to simulate this formula on computer ghaphics?

This is the geometry of space-time in 11 dimensions, in respect to perspective system. You will have a 5D-space, mirrored with the inverted limit of a pontual reference. There would be a universe ...
8
votes
1answer
105 views

Validity problem of intuitionistic two-variable logic

The two-variable fragment $\mathrm{FO}^2$ consist of those sentences of first-order logic $\mathrm{FO}$ in which precisely two variables occur (e.g. $\exists x \exists y \exists z R(x,y,z)$ is not a ...
0
votes
1answer
63 views

Is a grid graph a vertex-minor of a complete graph?

Consider a graph $G$. A graph $H$ is the vertex-minor of the graph $G$ if $H$ can be obtained from $G$ using vertex deletions and local complementations. For more information, look at Definition 2.1 ...
2
votes
0answers
46 views

Bin packing with non-additive load functions

I am looking for information on the bin packing problem, where the load of each bin is not the sum of items in the bin, but some other monotone set function. For example, suppose each item $i$ has ...
10
votes
1answer
474 views

Swapping arguments of variables in higher-order pattern unification

Pattern unification is a simplified form of higher-order unification in which existential variables only appear applied to distinct universal variables. Thus, for instance, an equation such as $M \,x\...
1
vote
0answers
49 views

Computational complexity of factoring univariate polynomials with positive integer coefficients

I am interested in the computational complexity of the following problem. Input: a polynomial p(x) with positive integer coefficients Output: a factorization of p(x) into irreducible factors having ...
8
votes
0answers
103 views

improved analysis of spectral gap of zigzag product?

I am reading the paper introducing zigzag products of expander graphs (https://arxiv.org/abs/math/0406038). The paper mentions the following observation in the introduction: Moreover, the variational ...
0
votes
1answer
59 views

Deterministic communication complexity of refinement

A partition of $[n]$ is a collection $\mathcal{P}$ of non-empty subsets of $[n]$ such that for each $i \in [n]$ there is a unique $P \in \mathcal{P}$ with $i \in P$. For partitions $\mathcal{P}, \...
1
vote
0answers
41 views

Properties of half-way locally bijective homomorphisms between Eulerian orientations

Short Version Let $G$ and $H$ be two Eulerian graphs and let $\overrightarrow{G}$ and $\overrightarrow{H}$ be Eulerian orientations of those graphs. Let $f$ be a homomorphism from $G$ to $H$. (...

15 30 50 per page
1
2 3 4 5
233