# Tag Info

0

Can I prove certain properties (that are guaranteed to hold) for a program (e.g., a subroutine is non-entrant and can never call itself) that allow to perform optimizations that are not usually possible. It is equivalent to extending the typechecker to provide some properties of a program to the optimizer. I believe Tsuyoshi Ito is right and you may ...

4

You're essentially asking for resources that will let you turn your existing knowledge of logic, recursion theory, and category theory into knowledge about theoretical computer science.I would suggest looking at realizability theory, especially via its connections to topos theory and categorical proof theory. Here are a handful of suggestions; my advice is ...

3

Get Spinrad's book on efficient graph representations: http://www.amazon.com/Efficient-Representations-Fields-Institute-Monographs/dp/0821828150 Also check out Li and Vitanyai's book on Kolmogorov Complexity: http://www.amazon.com/Efficient-Representations-Fields-Institute-Monographs/dp/0821828150 You will get an appriciation for each graph class by ...

5

In this paper graphs in which the size of every minimal separator $|S| \le k$ are called graphs of separability at most $k$. Theorem 1 of that paper implies that chordal graphs of separability at most $2$ are obtained from complete graphs by "gluing" along a vertex or an edge.

8

Probably the simplest approach is to perturb the edge weights symbolically rather than numerically. Intuitively, you'd like to reassign the weight of each edge as $$\tilde{w}(e) = w(e) + \varepsilon \cdot w'(e)$$ where $w(e)$ is the original edge weight, $w'(e)$ is a secondary edge weight, and $\varepsilon$ is a global scaling factor. This perturbation ...

-1

heres another angle based on some more search. a principle historical/emerging nexus/intersection between economics and computer science/complexity theory is computing Nash equilibria which are central to various economics models, where Daskalakis (collaborating with Papadimitriou) is a leading figure.[1][2][5] this overlap generally occurs through the ...

6

Main stream game theorists are, I think, becoming much more open to contemporary work in the computer science community, so it may be less necessary to "make the case'' for algorithmic game theory than it has been in the past. One of the texts that I know of that is most accessible to auction theorists with an economics background is Jason Hartline's ...

9

I see two separate directions to take your question. One is How has a computer science philosophy and computational thinking impacted the field of economics, and why should economists care about the computer science approach? This is a really cool but really broad question that I'll avoid attempting to address. The second is more specific: Now that computer ...

-4

this is clearly a very emerging area so surveys and established literature would be difficult to come by. also complexity theory may be a little more abstract for this. however a compelling/natural area on the rise/intersection between CS/econ: try recent research into auctions which is especially significant given google Adsense advertising largely funding ...

3

As Suresh says in his comment, you can extract the closest pair from the additively-weighted Voronoi diagram of the centers of the balls. The closest pair of balls (in your case, diamonds) will have adjacent Voronoi regions. The additively weighted Voronoi diagram of $n$ points in the plane can be constructed in $O(n\log n)$ time with high probability ...

1

Integer factorization is widely considered the best candidate for one way functions and it is in TFNP. From the abstract of this paper, Does the Polynomial Hierarchy Collapse if Onto Functions are Invertible?, it gives a relativized negative result by constructing an oracle under which TFNP functions are efficiently computable but the polynomial-time ...

0

This paper is not a humorous theory paper, but it is a really humorous paper by a theoretician, about dangers of being sloppy about punctuation. For example, in bibliography, he spelled his own name as: J. Dullman (As most reader know, Ullman's middle initial is D.) I can't recall the full details (issue, year #, page), but it appeared in SIGACT ...

1

Bruce Reed, Mangoes and Blueberries, Combinatorica 19 (1999) 267-296 .

1

Erik Demaine, et al 2008, provided the bidimensionality framework and by use of this framework they solved broad range of problems with sub exponential FPT algorithms, which directly deduces, sub exponential algorithms for many NPC problems on graphs of bounded genus and fixed H-Minor free graphs. Most important paper in the field is : Subexponential ...

4

This paper, Computational complexities of Diophantine equations with parameters by Tung, proves co-NP-completeness of a variant with parameters over natural numbers.

3

Note that it depends a lot on what set are you solving over. For example, the NP-complete SUBSET-SUM problem can be considered as a LINEAR DIOPHANTNE EQUATION, when you restrict your solution over positive integers. If you allow also negative solutions then it is solvable in polynomial time. For an excellent survey, see: ...

6

If $X_1, \cdots, X_n$ are $k$-wise independent random variables on $[0,1]$, then $$\text{Pr} \left[ \left| \sum_i X_i - \text{Ex}\left[ \sum_i X_i \right] \right| \geq n \cdot \varepsilon \right] \leq \left( \frac{k^2}{4 n \varepsilon^2} \right)^{\lfloor k/2 \rfloor}.$$ Note that this bound does not necessarily improve with greater $k$. So you may want to ...

4

This is the first link on Google for the search "chernoff limited independence": "Chernoff-Hoeffding Bounds for Applications with Limited Independence" by Schmidt et al.

5

First: all your inputs are either 0 or 180, and the midpoint gate always gives a point on the arc between its two inputs. So any intermediate value stays on the arc between 0 and 180, there is never wrap-around, and we may just assume that each input is a bit and the gates return $(a+b)/2$. Then there is a gate at the top that tests whether its input is in a ...

2

One of my favorites, Jan vondrak's thesis and many of his papers.

4

I do not know references for the quantified fragment but your problem is not the same as deciding well studied fragments of Presburger arithmetic because you have unit coefficients. The paper below by Pratt studies the case where constraints are of the form $x + c < y$, where $x$ and $y$ are variables and $c$ in a natural number. He shows that the ...

5

A single alternation in Presburger arithmetic is enough to obtain exponential lower bounds, more precisely formulae as in the question with $m=1$ and $n$ not fixed suffice (Grädel 1989).

6

The question of truth in Presburger Arithmetic with bounded quantifier alternation has been answered with quite some precision by Reddy and Loveland: C.R. Reddy & D.W. Loveland: Presburger Arithmetic with Bounded Quantifier Alternation. The paper may be found here (sorry for the ugly link). Their main result is stated as follows: The membership in ...

4

I would like to add "Submodular Functions and Electrical Networks" by H. Narayanan.

Top 50 recent answers are included