Skip to main content

All Questions

Filter by
Sorted by
Tagged with
1 vote
0 answers
48 views

Reference request: proof theory in $W_1^1$

Buss defined $V_2^1$​ as a second-order bounded arithmetic corresponding to $\mathsf{PSPACE}$. Later, Skelley introduced $W_1^1$​, a third-order simple bounded arithmetic. of $\mathsf{PSPACE}$. Since ...
palala's user avatar
  • 11
1 vote
0 answers
28 views

Integral hull of a polyhedron Q is polyhedron

Let $Q \subseteq R^n$ be a rational polyhedron and let $Q_I=Convexhull(Q \cap Z^n)$. By finite basis theorem, we have $Q=P+C$ for some rational polytope $P$ and finitely generated cone $C$ where $C=R_+...
Sowbarnika R's user avatar
-1 votes
0 answers
41 views

Is it possible to backtrack an optimization solver? [closed]

I have an optimization problem and was using a linear programming optimizer to find solutions. However, I find that past a certain size, the problem becomes "infeasible" and has no solutions....
Bamboozle's user avatar
3 votes
0 answers
94 views

What is the smallest known number of states that a one-way cellular automaton needs to be universal?

We know there is an elementary cellular automaton (ECA) with 2 states (Rule 110) that is universal, i.e. Turing-complete. One-way cellular automata (OCA's) are a subcategory of ECA's where the next ...
Joshua Holden's user avatar
0 votes
0 answers
57 views

Complexity of evaluation of analytic functions

Given an analytic function $f(x)$ (say as combination of elementary functions and operators), is it possible to compute $n$ first bits of the value of the function on the whole interval $[a, b]$ ...
roignoirewg's user avatar
0 votes
0 answers
21 views

Easy instance of set cover

I am trying to prove that a natural greedy algorithm solves the following instance of the set cover problem: for a set of elements $e\in U$ with a set of weights $w_e$, we define the cost of a subset ...
Tom Solberg's user avatar
  • 4,049
3 votes
1 answer
103 views

References: rigorous algorithms for elementary computations in base-b with complexity estimates

Definitions/Notation: Fix positive integers $b$ and $M$. Consider the set of real numbers which can be exactly expressed with $2M+1$ coefficients in base $b$, defined by $$\mathcal{X}(b,M):=\{x\in \...
ABIM's user avatar
  • 5,405
3 votes
0 answers
120 views

References on P vs NP under various axiomatic systems

I am teaching algorithms and theory of computation this semester and had the opportunity to dig a bit into the details of one way functions and the P vs NP problem. This problem has resisted attacks ...
ode's user avatar
  • 31
1 vote
1 answer
240 views

The equation $ax^2 +by^2 =1 \mod P$ in cyclotomic field

Let $L$ be a cyclotomic field, and $P$ a prime ideal of $\mathcal{O}_L$. is there any symbol for the equation $ax^2 + by^2 =1 \mod P$ and if so, is it computable in polynomial time? if $a$ is ...
Don Freecs's user avatar
7 votes
2 answers
242 views

Prove that $ n \leq d+1 $ under ordering constraints in $\mathbb{R}^d$

Let $x_1, \dotsc, x_n \in \mathbb{R}^d$ and $\theta_1, \dotsc, \theta_n \in \mathbb{R}^d$ be vectors such that for every $k \in [n]$, the following inequality holds: $$ \langle x_k, \theta_k \rangle &...
Alireza Bakhtiari's user avatar
1 vote
1 answer
217 views

What is the fastest known algorithm for evaluating a homogeneous binary polynomial?

This question was initially posted on math.stackexchange.com, but there is no appropriate answer, hence I have the right to publish it here again. Let $f(x,y) = \sum_{i = 0}^d f_i x^i y^{d-i}$ be a ...
Dimitri Koshelev's user avatar
1 vote
0 answers
37 views

Computing all roots of a function with square-root terms

Given $3n$ positive numbers $a_1, \ldots, a_n$, $b_1, \ldots, b_n$, and $x_1, \ldots, x_n$, we are given a function $$f(x) = \sum_{i = 1}^n \frac{a_i}{\sqrt{(x - x_i)^2 + b_i}}.$$ Can we find all the ...
Abheek Ghosh's user avatar
1 vote
0 answers
54 views

How computationally efficient are kernel tricks? [closed]

"If we compare to non-kernel polynomial regression it is O(Tnp) where is p is dimension of polynomial while kernel polynomial is O(n^2d) + O(T*n^2) where d is original number of attributes, ...
Saransh Gupta's user avatar
5 votes
0 answers
75 views

What is the maximal advantage of randomized over deterministic algorithms for approximation in the worst-case?

Let $X\subset Y$ be Banach spaces and $B_X:=\{x\in X: \|x\|_X\le1\}$ be the unit ball of $X$. The goal is to find an approximation of every element from $B_X$ with error measured in $Y$ by using at ...
Mario Ullrich's user avatar
5 votes
1 answer
264 views

What oracles make finding isomorphism (of finite structures) easy?

Below, all structures are finite, in a finite language, with underlying set an initial segment of the natural numbers. This has been edited to fix errors pointed out by Emil Jerabek in his answer ...
Noah Schweber's user avatar
5 votes
1 answer
264 views

Approximation of Hamiltonian cycles

Let's define the $\texttt{MinHalfSimpCycle}$ search problem: Given $G=(V, E)$ a complete, undirected graph with weights on the edges. We want a simple cycle in $G$ (each vertex appears in it at most ...
Beduin's user avatar
  • 53
2 votes
4 answers
212 views

Efficient algorithm for graph problem

Let $D=(V,E)$ be a directed graph, $S,T\subset V$ and $f:V\rightarrow \{1,\ldots, k\}$ a positive, bounded weight-function and $l\in \mathbb{N}$, find a path $v_1,\ldots, v_l\in V$ with $v_1\in S$ and ...
Martin Clever's user avatar
1 vote
1 answer
106 views

Iterated optimal transport

Suppose we are interested in two consecutive transport plans (in the Kantorovich formulation). That is, we are given finite sets $X$, $Y$ and $Z$, endowed with probability measures $\mu_X$, $\mu_Y$ ...
tex.support's user avatar
0 votes
0 answers
72 views

Klondike Solitaire as an NP-complete game

I am not a mathematician. I am trying to understand if the paper "The complexity of solitaire" that shows this game is NP-complete also has a implicit assumption that a given hand can only ...
Syl's user avatar
  • 1
0 votes
0 answers
37 views

Does the same hardness with access to different oracles imply equivalent oracles?

If $\textrm{coNP}^{\textrm{NP}}=\textrm{coNP}^{L}$ for $L\in\textrm{NP}$, then does that make $L$ NP-complete?
Rincewind's user avatar
0 votes
0 answers
60 views

Understanding "A Note on a Theorem by Ladner"

I'm reading A Note on a Theorem by Ladner by Balcazar and Diaz, trying to understand the proof of Theorem 2.1. I don't know if it's just old notation, but I'm having quite a bit of trouble. In step (...
Rincewind's user avatar
1 vote
0 answers
114 views

Simultaneous elimination of variables in multiple polynomials

I have a system of $n=O(1)$ non-homogeneous polynomials of total degree $d=O(1)$ $p_1,\dots,p_r\in \mathbb Z[x_1,\dots,x_n]$. I would like to eliminate $n-1$ variables simultaneously from the $n$ ...
Turbo's user avatar
  • 13.9k
1 vote
0 answers
92 views

Proof for non-existence of short integer program for squares

We do not know if $P=NP$ or not or if there is a superfast integer mutiplication algorithm. But I do not think either assumption is necessary to answer this question. Is there a way to show within an ...
Turbo's user avatar
  • 13.9k
6 votes
2 answers
276 views

Extending polynomial hierarchy above $\omega$

The arithmetic hierarchy is naturally extended to all ordinals via ordinal notations creating a hierarchy for all hyperarithmetic sets. The polynomial time hierarchy is defined analogously to the ...
Peter Gerdes's user avatar
  • 3,029
3 votes
0 answers
146 views

Lower Bound of Solutions to P=NP?

Do we at least know that simulating polynomial time non-deterministic Turing machines requires more than a linear slowdown? That is, do we know there is some non-deterministic Turing machine with ...
Peter Gerdes's user avatar
  • 3,029
1 vote
0 answers
69 views

Is it in theory possible to perform general Miller’s algorithm inversion as used with the optimal ate pairing with large trace in subexponential time?

Let’s I have the following : 2 curves $G_1$ defined on $F_p$ and $G_2$ being the $G_1$ curve’s twist defined on $F_p^2$ both having the same prime order ; a large trace ; and $F_p^{12}$ as their ...
user2284570's user avatar
2 votes
0 answers
95 views

Why cannot we adapt Barvinok type counting techniques to general convex integer programs?

Decision problems in Integer Linear Programming have Lenstra type algorithms (https://www.math.leidenuniv.nl/~lenstrahw/PUBLICATIONS/1983i/art.pdf) have been generalized to convex integer program ...
Turbo's user avatar
  • 13.9k
0 votes
0 answers
122 views

Is it in theory possible to create a subexponential algorithm for solving discrete logarithms in multiplicative subgroups or within an Integer range?

As far I understand, when it comes to finite fields, Pollard rho and Pollard’s lambda are still the best algorithm for solving discrete logarithms in a multiplicative subgroup/suborder… Index calculus ...
user2284570's user avatar
2 votes
0 answers
78 views

Is this variant of post correspondence problem undecidable?

The post correspondence problem, as defined by wikipedia, is undecidable. The problem is defined as follows. Let $A$ be an alphabet with at least two symbols. The input of the problem consists of ...
dips_123's user avatar
-2 votes
1 answer
181 views

What is the computational complexity to verify a P solution with a deterministic Turing machine? [closed]

As we know, NP (nondeterministic polynomial time) is a complexity class used to classify decision problems. NP is the set of decision problems for which the problem instances, where the answer is &...
XL _At_Here_There's user avatar
4 votes
1 answer
221 views

Recent research on polynomial identities

I work in computational complexity, where I work on the problem of polynomial identity testing over arithmetic circuits. One particular case is when the variables over the polynomial ring don't ...
Anagha's user avatar
  • 49
3 votes
1 answer
117 views

How to understand 'the problem of determining the exact number of monomials in P(x) given by a black box is #P-Complete'

In this paper: Michael Ben-Or and Prasoon Tiwari. 1988. A deterministic algorithm for sparse multivariate polynomial interpolation, In: Proceedings of the twentieth annual ACM symposium on Theory of ...
Youzhe Heng's user avatar
2 votes
0 answers
93 views

How are moduli spaces related to geometric complexity theory?

I am interested in understanding the relationship between moduli spaces and geometric complexity theory (GCT). Relation between moduli spaces and GCT: How are moduli spaces related to geometric ...
HasIEluS's user avatar
3 votes
1 answer
315 views

About Shor's quantum algorithm

I know very little about quantum computing, and I've been trying to understand Shor's algorithm for the factorization of an integer $N$. I'm following Computational Complexity — a modern approach by ...
Pierre's user avatar
  • 2,287
2 votes
0 answers
71 views

Lexicographically largest incidence matrix

I have simple algorithmic question, but I can't find any source where this algorithm is explained in details. Let's assume that we have incidence (with 0 and 1 values) matrix of size $m\times n$. Let ...
Ihromant's user avatar
  • 501
0 votes
0 answers
48 views

A question on a quantitative form of Farkas' lemma

Suppose A is an $m \times n$ matrix whose entries are non-negative integers and $\mathbf{b}$ is a vector with rational entries. A version of Farkas lemma implies that if the equation $$A\mathbf{x}=\...
Keivan Karai's user avatar
  • 6,214
3 votes
1 answer
329 views

Nonexistence of short integer program sequence which generates squares

Is there a way to show within an integer program with constant number of variables and constraints of length $poly(\log B)$ (say length $\leq10^{1000000}\log B$), it is not possible for a variable to ...
Turbo's user avatar
  • 13.9k
1 vote
0 answers
99 views

Minimum of the maximum element frequency given the family size and the universe size

[Crossposted at math.stackexchange]. Consider families of sets $\mathcal{F}$ with size $n = |\mathcal{F}|$ and universe $U(\mathcal{F})$ with size $q = |U(\mathcal{F})|$. I have written and solved ...
Fabius Wiesner's user avatar
8 votes
0 answers
164 views

Is there a substructure-preservation result for FOL in finite model theory?

It's well-known$^*$ that the Los-Tarski theorem ("Every substructure-preserved sentence is equivalent to a $\forall^*$-sentence") fails for $\mathsf{FOL}$ in the finite setting: we can find ...
Noah Schweber's user avatar
3 votes
2 answers
334 views

Algorithm to evaluate "connectedness" of a binary matrix

I have the following problem: given an $m \times n$ binary matrix $A$ like e.g. the following $9 \times 39$ matrix: ...
Fabius Wiesner's user avatar
3 votes
1 answer
80 views

On the relationship between graph isomorphism and equivalence in ETL workflow dependency graphs

$\newcommand{\inn}{\mathrm{in}}\newcommand{\out}{\mathrm{out}}$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'$) ...
user avatar
9 votes
1 answer
506 views

Current state of the art in geometric complexity theory

I came across this interesting question from almost 7 years ago: What are the current breakthroughs of Geometric Complexity Theory? My question is quite simple: Have there been any breakthroughs in ...
Bobby-John Wilson's user avatar
0 votes
0 answers
115 views

Software for computing polytopes

As can be inferred from the title, I want to do some computation on the facets representation of the polytopes given the vertices. My advisor recommended me Polymake, which is indeed useful even with ...
AlexiosF's user avatar
1 vote
0 answers
50 views

Computational complexity of deciding if two elements are in the same cycle of a permutation, version 2

This question has relation with this previous one, although the two cases are not likely solved with the same method. Let us consider a function $P:\{0,1\}^*\to\{0,1\}^*$ that can be calculated in ...
Doriano Brogioli's user avatar
5 votes
1 answer
175 views

Computational complexity of deciding if two elements are in the same cycle of a permutation

Given $n\in \mathbb{N}$, we have a bijection $P:\{0,1\}^n\to\{0,1\}^n$, i.e. $P$ is a permutation of $2^n$ symbols, $P\in S_{2^n}$. The permutation $P$ can be calculated efficiently, i.e. by a ...
Doriano Brogioli's user avatar
5 votes
1 answer
176 views

Efficient counting of integer solutions to linear system

In my research, I have a particular 18x18 matrix $\mathbf{A}$ which defines the linear system $\mathbf{A}\cdot \mathbf{x} \leq \mathbf{-1}$ over the nonnegative integers. And I'm interested in ...
user326210's user avatar
0 votes
0 answers
92 views

Algorithm that can solve or approximate the solution to a combination problem

I have a computational problem on my hands and I would like your help. Here is my problem (simplified) Let $X = \{x_1, x_2, \ldots, x_n\}$ represent a set of $n$ values. Each value $x_i$ has a ...
econ's user avatar
  • 1
13 votes
2 answers
555 views

Convergence of the sequence $s_{n+1}=s_n^2-s_{n-1}^2$

$s_{n+1}=s_n^2-s_{n-1}^2$, $s_0=\sqrt{x}$, $s_1=x$ This sequence seems simple, but is pretty confusing. If you try it with integers, you might think that it always diverges to infinity, but if you try ...
look at me's user avatar
2 votes
0 answers
116 views

Reference for a coarse complexity notion

Throughout, I'm only interested in structures with domain $\mathbb{N}$, no primitive relations, and at least $0,\mathsf{Succ}$ as primitive functions. The length of $m\in\mathbb{N}$ is $\lfloor 1+\...
Noah Schweber's user avatar
2 votes
0 answers
172 views

NP-hardness of a string transformation problem with k templates

Given strings $x$ and $y$, a template length $l$, and a maximum number of different templates $k$, the task is to determine if it's possible to convert $x$ into $y$ using no more than $k$ different ...
Paul Calvi 's user avatar

1
2 3 4 5
37