^January February – 2012 ^March

An important feature of web search interfaces are the restrictions enforced on input values – those reflecting either the semantics of the data or requirements specific to the interface. Both integrity constraints and “access restrictions” can be of great use to web exploration tools. We demonstrate here a novel technique for discovering constraints that requires no form submissions whatsoever. We work via statically analyzing the JavaScript client-side code used to enforce the constraints, when such code is available. We combine custom recognizers for JavaScript functions relevant to constraint-checking with a generic program analysis layer. Integrated with a web browser, our system shows the constraints detected on accessed web forms, and allows a user to see the corresponding JavaScript code fragment.

Making faultless complex objects from potentially faulty building blocks is a fundamental challenge in computer engineering, nanotechnology and synthetic biology. We show for the first time how recursion can be used to address this challenge and demonstrate a recursive procedure that constructs error-free DNA molecules and their libraries from error-prone oligonucleotides. Divide and Conquer (D&C), the quintessential recursive problem-solving technique, is applied in silico to divide the target DNA sequence into overlapping oligonucleotides short enough to be synthesized directly, albeit with errors; error-prone oligonucleotides are recursively combined in vitro, forming error-prone DNA molecules; error-free fragments of these molecules are then identified, extracted and used as new, typically longer and more accurate, inputs to another iteration of the recursive construction procedure; the entire process repeats until an error-free target molecule is formed. Our recursive construction procedure surpasses existing methods for de novo DNA synthesis in speed, precision, amenability to automation, ease of combining synthetic and natural DNA fragments, and ability to construct designer DNA libraries. It thus provides a novel and robust foundation for the design and construction of synthetic biological molecules and organisms.

All living cells use very large protein assemblies to carry out complex tasks. The structural understanding of these efficient nano-machines is often very limited, because conventional techniques like X-ray crystallography or cryo-EM cannot resolve them to sufficient resolution. Firsthand knowledge with cases where the low resolution resulted in limited or even wrong biological conclusions, had led us to the realization that completely unbiased methods are essential. To that end, we developed a combinatorial approach that exhaustively enumerates all the possible arrangements of the biological system and assesses them objectively against the structural data. I will present two such applications on a very suitable system: the eukaryotic chaperonin TRiC/CCT. This large complex is essential to the correct and efficient folding of many proteins in our cells. The overall structure is a spherical particle made of sixteen different subunits, whose exact arrangement was hitherto unknown. We have modeled all the 40,320 possible arrangements and compared them to two sets of structural data: (i) cross-linking and mass-spectrometry and (ii) crystallographic dataset at 3.8.. Both sets have single out the same arrangement, which to our surprise was very different than any previous model suggested for TRiC.

World Wide Web, the Internet, biology PPI networks, and social networks, are only a few examples of networks that contain characteristic patterns, termed network motifs, which occur far more often than in randomized networks with the same degree sequence. Our first set of results is related to motif local counting, namely, counting the number of motifs a vertex is part of. We present several efficient algorithms that approximate the local number of occurrences of k-length cycles and k-length cycles with a chord, where k = O(log n). We also provide efficient algorithms that approximate the local number of occurrences of all motifs of size of at most four.Our second set of results relates to general approximate motif counting. We design sublinear algorithm for approximating the number of copies of constant-size stars in a graph. We prove that our algorithm is tight up to polylogarithmic factors. Our work extends the work of Feige and Goldreich and Ron on approximating the number of edges (or average degree) in a graph. In addition, we give some (negative) results on approximating the number of triangles and on approximating the number of length-3-paths in sublinear time.

Personalized treatment approaches which optimize drugs doses according to pre-treatment and early response-to-therapy evaluation hold the promise to improve treatment success rates and reduce severe adverse side-effects due to drugs toxicity in variety of pathologies. Reliable assessment of tissue microenvironment including cell proliferation, density and size and tissue perfusion as a biomarker for disease activity is a key necessity for personalized, response-based treatment regimes. Histology-based tissue microenvironment analysis requires invasive, surgical procedure to obtain the tissue sample. Moreover, the histological analysis is limited to the obtained tissue sample which may not be sufficient in heterogeneous microenvironment. Instead, we developed the TM-MRI method utilized short-duration free-breathing diffusion-weighted MRI acquired with multiple b-values coupled with global tissue microenvironment model and reliable fitting technique that enables radiation and toxicity-free non-invasive insight into the entire three-dimensional tissue microstructure. In the lecture I’ll present the core components of this method: 1) the TM-MRI image acquisition scheme; 2) the global tissue microenvironment model, and; 3) reliable model fitting technique with intrinsic fit-quality assessment. In addition, I'll present initial clinical results of non-invasive disease activity assessment using the TM-MRI quantitative biomarkers in pediatric Crohn’s disease patients and discuss future applications of this technique.

The doubling dimension is a natural measure of the richness of a metric space. It was first considered by Assouad in the context of metric embeddings, and has since found its way into the algorithms and machine learning communities. Ultimately, the doubling dimension provides a way to generalized many results tailored for low-dimensional Euclidean space to apply to more general metric space. The Traveling Salesman Problem (TSP) is among the most famous NP-hard optimization problems. We design for this problem a randomized polynomial-time algorithm that computes a (1+eps)-approximation to the optimal tour, for any fixed eps>0, in TSP instances that form an arbitrary metric space with bounded intrinsic dimension. The celebrated results of Arora (A-98) and Mitchell (M-99) prove that the above result holds in the special case of TSP in a fixed-dimensional Euclidean space. Thus, our algorithm demonstrates that the algorithmic tractability of metric TSP depends on the dimensionality of the space and not on its specific geometry. This result resolves a problem that has been open since the quasi-polynomial time algorithm of Talwar (T-04).

Structured Prediction is a branch of Machine Learning which is concerned with prediction of complex outputs, such as sequences, trees and graphs, with applications in Natural Language Processing, Computer Vision and Computational Biology. Most structured prediction inference problems are intractable, and as a result many algorithms sacrifice model expressivity (i.e. the kinds of informations that can be taken into account when making predictions) in favor of polynomial-time exact inference. I advocate a different framework, in which exact inference is sacrificed in favor of expressive models. Instead of being trained to optimize a global objective function, the models are trained to make a sequence of greedy locally-optimal decisions, while taking easier choices before harder ones, and relaying on earlier predictions do disambiguate later ones. The resulting algorithms are very fast while remaining competitive in terms of prediction accuracy.

This talk is going to show some of the new and cool hacking & security topics. 3 main topics will be presented. It would be focus on the hacking part and would include topics as TV cable hacking, Hardware hacking, SCADA and the 4 top ways to get infected from the internet.