All Questions

-2
votes
0answers
7 views

Prove A ⋄ B := {xy|x ∈ A, y ∈ B, |x| = |y|} is context-free without using PDA [on hold]

For any regular languages A, B, A ⋄ B := {xy|x ∈ A, y ∈ B, |x| = |y|}. Prove that A ⋄ B is context-free. So far: I know how to show that the reverse of L is regular. And then I need to build a CFG ...
-3
votes
0answers
9 views

If f(n) is Big Theta of g(n), then are they also both lower bounds of each other? [on hold]

Is it necessarily true that if: $f(n) = \Theta(g(n))$ Then $f(n) = \Omega(g(n))$ and $g(n) = \Omega(f(n))$
0
votes
0answers
16 views

Is there a standard name for this way of modifying graphs?

Let $G = (V, E)$ be an undirected graph. Let me take an edge $\{x, y\}$ (in blue in the drawing) such that $x$ and $y$ have other incident edges. Among the incident edges we choose one edge $e_x = \{...
0
votes
0answers
17 views

Complexity of #PP2DNF where we also count on the number of clauses

The #PP2DNF problem is the following: we have variables $X = \{x_1, \ldots, x_n\}$, $Y = \{y_1, \ldots, y_n\}$, and a positive partitioned 2-DNF formula, i.e., a Boolean formula of the form $\phi = \...
-1
votes
0answers
24 views

Is nand a counterexample to Lawvere’s fixed point theorem for the 2 point set?

To quote Lawvere (Conceptual Mathematics, p. 305) “Applying Cantor's Theorem we can conclude that no map T x T —>2 can parameterize all maps T —>2.” But nand would seem to be such a map. It maps 2 x 2 ...
-2
votes
0answers
19 views

How to prove Euler formula for graph theory? [on hold]

How to prove Euler formula for hypergraph? How we defines faces in hyper graphs ?
5
votes
0answers
32 views

Can we define a meaningful concept of exptime reductions (as opposed to polytime reductions) for classes like NEXP or NEEXP?

Typically we are only interested in polytime reductions as we are usually interested in showing a reduction from one NP problem to another. However, if we consider larger complexity classes such as ...
1
vote
0answers
29 views

Complexity of planted root of a system of quadratic homogeneous polynomials?

Given homogeneous degree $2$ algebraically independent polynomials $f_1,\dots,f_{m}$ in $\mathbb Z[x_1,\dots,x_n,y_1,\dots,y_n]$ each with only monomials $x_iy_j$ with condition that the system $f_1=\...
3
votes
0answers
76 views

What is the hardest instance for the group isomorphism problem?

Two groups $(G,\cdot)$ and $(H, \times)$ are said to be isomorphic iff there exists a homomorphism from $G$ to $H$ which is bijective. The group isomorphism problem is as follows given two groups ...
0
votes
0answers
35 views

Enumerate over all halting Turing Machines? [on hold]

I understand that it is possible to enumerate over all Turing Machines. My understanding of how this works is by fixing an encoding of natural numbers to TM descriptions, and then enumerating the ...
1
vote
0answers
30 views

Problems rephrased as quadratic unconstrained binary optimization

I was impressed when i came across Quadratic unconstrained binary optimization (QUBO) recently, and saw how one can rephrase many combinatorial problems into questions about optima of binary functions....
0
votes
0answers
28 views

First-order multi arity functions in dependent type?

(cross posted from Reddit https://www.reddit.com/r/dependent_types/comments/b1ts8b/firstorder_multi_arity_functions_in_dependent_type/? Take Agda for example, functions of multi arity is "encoded" as ...
1
vote
0answers
39 views

Inexpressibility of Second order

In finite model theory, Ehrenfeucht-Fraïssé games gives us tools to prove inexpressibility results for FOL. Pebble games do the same for infinitary logic with finitely many variables. Do we have such ...
4
votes
0answers
84 views

An axiom for John Major's Equality

In the the standard library of Coq, there is the axiom: Axiom JMeq_eq : forall (A:Type) (x y:A), JMeq x y -> x = y. Why isn't it provable? Can it be reduced ...
3
votes
1answer
89 views

How is SDP an extension of spectral algorithms?

In one of his lectures, Uri Feige described semidefinite programming (SDP) as ... an algorithmic technique that extends both linear programming and spectral algorithms. I know the basic ...
-2
votes
0answers
38 views

Why does Chaos Improve Evolutionary Algorithms?

I have presented an evolutionary algorithm using chaos theory (chaotic numbers) to solve an optimization problem. The results of the experiments show that this algorithm is much better than the same ...
-1
votes
0answers
8 views

Fastest way to read large wav files (or any large file) to python [migrated]

So i'm working on a school project where i have to work with large wav files ( > 250Mgb), and i wonder, why when i read such a file to audacity software, it take about 40 sec to be read and ploted, ...
1
vote
0answers
36 views

Corruption bound in communication complexity

The corruption bound is referenced in this paper by Sherstov. Theorem 6 (Corruption bound): Let $f : X × Y \rightarrow \{0, 1\}$ be a given function and $\alpha, \beta \ge 0$ be given parameters. ...
-2
votes
0answers
19 views

How to calculate the number of variables and total number of clauses in a SAT problem for a specific domain size? [on hold]

I have a set of propositional clauses generated by clausification of a set of first-order logic axioms containing 2 binary predicates (p and c). Assume P is the number of distinct predicates in the ...
2
votes
1answer
93 views

Intuitive explanation behind Goemans-Williamson randomized rounding

A very simple randomized cut algorithm achieves $1/2$ of the optimal value: just choose each vertex to be in the cut with probability $1/2$, independently. Goemans-Williamson does something more ...
3
votes
1answer
70 views

Compressing grammars by introducing ambiguity and left-recursion

This is a reference request. What is known about the following questions? Problem: Given a grammar $G$ (for example context-free) with language $L$ we can introduce a new grammar $G'$ which also ...
0
votes
0answers
72 views

Universality exists? [closed]

Do universal computers exist?
-1
votes
0answers
53 views

greedy performance

I have a set function $f:2^V\rightarrow R_+ $which is non negative monotone supermodular function with a property that $f(\{x\})$ is same for all $x\in V$($f(\{x_1\})=f(\{x_2\})=\dots =f(\{x_i\}),\...
3
votes
0answers
51 views

Are there experiments in artificial life on the emergence of sexual reproduction (analogues)?

I'm aware of quite a few experiments on the emergence of replicators in various artificial life areas, e.g. from cellular automata to computer programs. Have any similar result been obtained on the ...
1
vote
0answers
47 views

Confusion about the visibility and arbitration relations in a formal framework for distributed consistency models

In the POPL'14 paper "Replicated Data Types: Specification, Verification, Optimality" and the book "Principles of Eventual Consistency", the authors propose a formal framework for specifying ...
1
vote
1answer
68 views

The SQ argument in Balazs Szorenyi's paper

I am asking about the proof in Theorem 5 (page 6) of this paper, http://www.inf.u-szeged.hu/~szorenyi/Cikkek/sq_d0_ext.pdf Quite a few things about this short argument seem unclear to me, Towards ...
0
votes
1answer
41 views

Counting sum of parities of cycle covers in cubic, planar, bipartite graphs

Let $G$ be a cubic (i.e. every degree exactly three), planar, bipartite graph. By Hall's theorem its edges can be partitioned into three perfect matchings. Take any such partition $M_0,M_1,M_2$ and ...
4
votes
0answers
70 views

Is there a universal gate set for classical probabilistic computing?

We know that NAND gates are universal for deterministic classical circuits, Toffoli gates are universal for reversible deterministic classical circuits, and Clifford+T is universal for quantum ...
1
vote
1answer
97 views

Optimal bounds for $k$-wise non-uniform random bits

Let $k\geq 2$ be a constant (in my case, $k=4$), and $n,t \geq 0$ be integers such that $2^t \leq n$. What is the smallest sample space (or, equivalent, how many true independent random bits are ...
3
votes
0answers
129 views

Take a NEXP-complete problem and then have the input in unary. Why is this not NP-complete?

It is known that if any unary language is NP-complete, then P=NP. Suppose we take a NEXP-complete language with input $x$ in binary and witness $y\in\{0,1\}^{2^{poly(|x|)}}$ such that the verifying ...
8
votes
0answers
175 views

Subset sum problem with at most one solution for any target

This question was originally asked on CS.se. A little bit of initial discussion can be found in the comments there. We first consider the search version of the subset sum problem: Given a set $S$ of ...
4
votes
0answers
127 views

Why is the Toffoli Gate named after Toffoli?

I was reading the following paper: Rolf Landauer, Irreversibility and Heat Generation in the Computing Process, IBM Journal of Research and Development, Volume 5, Issue 3, July 1961. On page 4, ...
-2
votes
0answers
16 views

Why do functions in Vimscript require a “call” statement? [migrated]

In Vimscript, if you use a function as an R-value, then the function simply evaluates. For example: let count_pattern += str2nr( strpart( execute( command ), 1 ) ) ...
11
votes
0answers
165 views

Computational Complexity of the Frobenius Problem

The Frobenius problem takes as input $n$ positive integers $a_1,\ldots,a_n$ with $\gcd(a_1,\ldots,a_n)=1$ and asks for the largest integer $F$ that cannot be written in the form $F=a_1x_1+a_2x_2+\...
1
vote
2answers
72 views

Enumerate all allocations of points in a simplex

Consider the standard 2-simplex $\{(x,y)~|~x+y=1~;~ x,y\geq 0\}$. Given a set $M$ of $m$ points in this simplex, we allocate each point either to X or to Y by the following process: Fix two positive ...
1
vote
1answer
70 views

3 dimensional matching shortest solution NP-hard?

We have array of arbitrary number of elements - 3d vectors with positive integers components - for example ...
-1
votes
0answers
22 views

Learnability proof for lower dimensional joint vector space

For a multi-label learning problem, if I have a mapping function which takes in documents and labels and maps them to a lower dimensional joint vector space, how do I prove that this space is ...
3
votes
0answers
55 views

Probability of detecting small bias of a die in the low confidence regime / balls and bins

We are given a biased $m$-sided die: one of the sides has probability $\frac{1}{m} + \gamma$ and all the rest have probability $\frac{1}{m} - \frac{\gamma}{m-1}$ each. The goal is to figure out which ...
1
vote
0answers
33 views

Minimising the maximum distance to the centre of a cluster of points

I have a set of points $C_i$ on a two dimensional plane and I want to find a point $P$ such that the maximum distance from $P$ to any of the points is minimised, i.e. minimise(max($||P-C_i||$)). I've ...
-1
votes
0answers
27 views

Power of one step transition of a QTM

So in defining a quantum Turing machine, we have transition as below: $$ \delta:Q\times \Gamma\rightarrow \mathbb{C'}^{Q\times \Gamma\times\{L,R,0\}} $$ Where $\mathbb{C}'\subseteq\mathbb{C}$ is a ...
1
vote
2answers
94 views

When is a problem specified on a TM contained in non-uniform classes such as P/poly? [on hold]

In this paper by Gottesman and Irani: https://arxiv.org/abs/0905.2419 , they prove NEXP-hardness of tiling an $N\times N$ grid. They do so by encoding a TM in the tiles making up the grid. However, ...
6
votes
1answer
153 views

How to generalize VC dimension?

Let's try to generalize the $VC$-dimension (of the class of hyperplanes) to include accuracy/error. Let $S$ be a set of points in $R^d$ and $t$ in $[0,1]$. We say that the class of hyperplanes $t$-...
-1
votes
0answers
29 views

Precision Sampling for Heavy Hitters

This is an intermediate step to show that we can use precision sampling to estimate $l_1$ of a stream with help of heavy hitter. Say we have a bunch of random variables $u_i \sim \exp(1)$ for $i = 0, ...
-1
votes
0answers
107 views

$BPP$ before Adleman-Sipser-Gacs theorem?

Where was $BPP$ before it was in second level? If we show $BPP$ is in $P^{NP}$ then we would've separated $BPP$ from $EXP^{NP}$. What did $BPP$ in second level accomplish? Did it have to cross any ...
-1
votes
0answers
20 views

Approximate a Decision Function Using a Neural Network

I have 10 variables $Y_i$, $i=1,\dots,10$ for a data record and I want to classify that record into one of three groups. A suggested decision function is the following: Group 1 if: $Y_i=0$ for $i=1,\...
0
votes
0answers
76 views

Something wrong with showing the limitations of finite automata [on hold]

To show the limitation of finite automata (FAs) generally a non-regular language is given as an example such as $A=\{0^n1^n | n \ge 0 \}$. And it is shown that FAs cannot recognize this language. ...
6
votes
0answers
262 views

Search in a sorted matrix

A matrix $M$ is sorted if $M_{i,j}\leq M_{i+1,j}$ and $M_{i,j}\leq M_{i,j+1}$. Consider the following problem. Search in a sorted matrix Given a $n\times m$ sorted matrix $M$, where $n\leq m$....
0
votes
1answer
116 views

Data Strcuture to represent dependencies amongst modules

Consider several software modules $m_1, m_2, ... m_n$. Each module has some inputs and outputs and the inputs to some of the modules are dependent on the outputs of some other modes. For example, in ...
5
votes
2answers
99 views

Statistical Distance Growth Given K Independent Copies

Let $X$ and $Y$ be distributions with statistical distance (total variation distance) at most $d$. What is the best upper bound you can give on the statistical distance between $k$ independent copies ...
4
votes
0answers
65 views

Refinement of the hierarchy theorem of a complexity class

Say $\mathrm{CTIME}$ is some complexity measure, syntactic or semantic (e.g. $\mathrm{DTIME}$ or $\mathrm{BPTIME}$). If we already know that for some $f(n) = \omega(n)$, $\mathrm{CTIME}(n) \subsetneq \...

15 30 50 per page