Tag Info

New answers tagged

0

There is a very nice metaphor on decidable languages in the book Gödel, Escher, Bach by Douglas Hofstadter. He uses drawings as an analogy for recursively enumerable languages. Every time you draw something on a sheet of paper, the part of the sheet that is not used by your drawing can be viewed as the "complement" of your drawing. The artist M.C. Escher ...


0

Dijkstra's Algorithm and Human Psyche http://rkvsraman.blogspot.in/2005/12/dijkstras-algorithm-and-human-psyche.html


0

B-Trees, N-ary Trees, Autocracy and Democracy http://rkvsraman.blogspot.in/2008/08/b-trees-n-ary-trees-autocracy-and.html


0

Following http://arxiv.org/pdf/1502.05912.pdf sometimes grobner basis are used to decide isomorphism (when graphs are encoded by systems of equations). But this joins the use of grobner basis in refutating CNFS.


4

There are several relevant references on the subject. I just indicate a few of them. I suggest you to browse the references of these articles to get more. Early references include the work of Françoise Gire. [1] F. Gire, "Relations rationnelles infinitaires", Thèse de 3ème cycle, Paris VII, 1981. [2] F. Gire, Une Extension aux Mots Infinis de la Notion de ...


3

There has been some recent work in terms of characterizing automorphism groups of strongly regular graphs using asymptotic group theory (e.g. this paper), which (for many reasons) is likely very closely related to the complexity of algorithms on strongly regular graphs that use group-theoretic methods, although exploiting such properties algorithmically is ...


2

I'll provide a naive approach which give $O(m^2 \cdot max_f)$ running time but shows the problem is P. First turn the graph to undirected graph. Suppose one edge is in first graph and the other in the second graph, contract both of them and name them $s,t$. We can find a minimum edge cut that separates s and t in time max_f which is a running time of best ...


4

Here is a brief overview and introduction to steganography: Christian Cachin. Digital steganography. In Henk C.A. van Tilborg, editor, Encyclopedia of Cryptography and Security. Springer, 2005 Since you asked for an introduction specifically for information-theoretic approaches, you might try this paper as a starting point for more detail: Christian ...


8

I did this very thing — computer-assisted NP-completeness proof — in my bachelor thesis! The bad part - it's in Russian and wasn't translated to English. http://is.ifmo.ru/diploma-theses/_dvorkin_bachelor.pdf I worked with logical gates in 2D problems. The plan is: Manually design what a "wire" looks like in your problem. Use very smart and optimized ...


1

You might like to look at Bernstein, Buchmann, Dahmen (editors): Post-Quantum Cryptography. The idea of the book is to study what will be available when current methods will become insecure. The book arose via a discussion at an IPAM/UCLA workshop.


4

A good start would be Katz and Lindell's Introduction to Modern Cryptography. Alternatively, you might want to take one of the crypto courses on Coursera: I recommend the ones taught by Jonathan Katz and by Dan Boneh (search for "cryptography" on Coursera). They are both free.



Top 50 recent answers are included