Unprovable Security of Perfect NIZK and Non-interactive Non-malleable Commitments

We present barriers to provable security of two important cryptographic primitives, perfect non-interactive zero knowledge (NIZK) and non-interactive non-alleable commitments:

1. ○
   Black-box reductions cannot be used to demonstrate adaptive soundness (i.e., that soundness holds even if the statement to be proven is chosen as a function of the common reference string) of any statistical NIZK for NP based on any “standard” intractability assumptions.
    
2. ○
   Black-box reductions cannot be used to demonstrate non-malleability of non-interactive, or even 2-message, commitment schemes based on any “standard” intractability assumptions.
    

We emphasize that the above separations apply even if the construction of the considered primitives makes a non-black-box use of the underlying assumption.

As an independent contribution, we suggest a taxonomy of game-based intractability assumptions.     

Explaining Computation Without Semantics: Keeping it Simple

This paper deals with the question: how is computation best individuated?

1. 1.
   The semantic view of computation: computation is best individuated by its semantic properties.
    
2. 2.
   The causal view of computation: computation is best individuated by its causal properties.
    
3. 3.
   The functional view of computation: computation is best individuated by its functional properties.
    

Some scientific theories explain the capacities of brains by appealing to computations that they supposedly perform. The reason for that is usually that computation is individuated semantically. I criticize the reasons in support of this view and its presupposition of representation and semantics. Furthermore, I argue that the only justified appeal to a representational individuation of computation might be that it is partly individuated by implicit intrinsic representations.

     

Feedback affinization of nonlinear control systems

In this paper conditions for the nonlinear control system

to have a nonlinear feedback control

u=(x,v), vΩ′R^m′, m′m, 0Ω′

such that the nonlinear system takes a form of an affine system

are presented. All results require algebraic operations and differentiation of functions only.     

Stabilization and tracking in the nonholonomic integrator via sliding modes

In this paper we use an approach based on sliding mode control to design a feedback which stabilizes the origin for the so-called nonholonomic integrator or Heisenberg system, a particular case of a canonical class of nonlinear driftless control systems of the form

which fail Brockett's necessary condition for the existence of a smooth stabilizing feedback.     

Improving time-to-market using SDL tools and techniques

In this paper we summarize our experiences in building and integrating new generation, formal-methods based computer aided software engineering tools (CASE) to yield pragmatic improvements in software engineering processes in the telecommunication industry. We define an accelerated development methodology (ADM) for the specification, design, testing and re-engineering of telecommunications software. We identify two of the most significant barriers to adoption of tools and formal methods to speed up software development, namely the requirements engineering barrier and the legacy code re-engineering barrier, and show how the ADM methodology helps to overcome these barriers and improve time-to-market for telecommunications software.Our ADM methodology is based on the most widely accepted formal languages standardized by the International Telecommunications Union (ITU):

Full-size image

This paper emphasizes the following key components of our ADM methodology and their placement within the most common software engineering processes:

Full-size image

Empirical evaluation of the effects of experience on code quality and programmer productivity: an exploratory study

Context

There is a widespread belief in both SE and other branches of science that experience helps professionals to improve their performance. However, cases have been reported where experience not only does not have a positive influence but sometimes even degrades the performance of professionals.

Aim

Determine whether years of experience influence programmer performance.

Method

We have analysed 10 quasi-experiments executed both in academia with graduate and postgraduate students and in industry with professionals. The experimental task was to apply ITLD on two experimental problems and then measure external code quality and programmer productivity.

Results

Programming experience gained in industry does not appear to have any effect whatsoever on quality and productivity. Overall programming experience gained in academia does tend to have a positive influence on programmer performance. These two findings may be related to the fact that, as opposed to deliberate practice, routine practice does not appear to lead to improved performance. Experience in the use of productivity tools, such as testing frameworks and IDE also has positive effects.

Conclusion

Years of experience are a poor predictor of programmer performance. Academic background and specialized knowledge of task-related aspects appear to be rather good predictors.

     

Oscillation of forced neutral differential equations with positive and negative coefficients

Some sufficient conditions are obtained for the oscillation of forced neutral differential equations with positive and negative coefficients

where .     

The Complexity Ecology of Parameters: An Illustration Using Bounded Max Leaf Number

In the framework of parameterized complexity, exploring how one parameter affects the complexity of a different parameterized (or unparameterized problem) is of general interest. A well-developed example is the investigation of how the parameter treewidth influences the complexity of (other) graph problems. The reason why such investigations are of general interest is that real-world input distributions for computational problems often inherit structure from the natural computational processes that produce the problem instances (not necessarily in obvious, or well-understood ways). The max leaf number ml(G) of a connected graph G is the maximum number of leaves in a spanning tree for G. Exploring questions analogous to the well-studied case of treewidth, we can ask: how hard is it to solve 3-Coloring, Hamilton Path, Minimum Dominating Set, Minimum Bandwidth or many other problems, for graphs of bounded max leaf number? What optimization problems are W[1]-hard under this parameterization? We do two things:

1. (1)
   We describe much improved FPT algorithms for a large number of graph problems, for input graphs G for which ml(G)≤k, based on the polynomial-time extremal structure theory canonically associated to this parameter. We consider improved algorithms both from the point of view of kernelization bounds, and in terms of improved fixed-parameter tractable (FPT) runtimes O ^*(f(k)).
    
2. (2)
   The way that we obtain these concrete algorithmic results is general and systematic. We describe the approach, and raise programmatic questions.
    

     

Oscillations and nonoscillations of half-linear difference equations generated by deviating arguments

For the half-linear difference equation

where α > 0, we shall offer sufficient conditions for the oscillation of all solutions, as well as necessary and sufficient conditions for the existence of both bounded and unbounded nonoscillatory solutions. Several examples which dwell upon the importance of our results are also included.     

New oscillation criteria for second order linear difference equations with positive and negative coefficients

The oscillation of second order neutral difference equations with positive and negative coefficients of the form

is investigated. We obtain many new results using the comparison between both first order and second order difference equations. An example is given to show the strength of the obtained results.     

Compositional Restricted Multiple Access Channel

We introduce the notion of a q-ary s-compositional code and prove that the rate, R, of the best such code satisfies for large s the asymptotic inequalities

$$(q - 1)\frac{{{{\log }_q}s}}{{4s}} \lesssim 2(q - 1)\frac{{{{\log }_q}s}}{{4s}}$$

.

     

Incompressible Functions,Relative-Error Extractors,and the Power of Nondeterministic Reductions

A circuit C compresses a function \({f : \{0,1\}^n\rightarrow \{0,1\}^m}\) if given an input \({x\in \{0,1\}^n}\), the circuit C can shrink x to a shorter ?-bit string x′ such that later, a computationally unbounded solver D will be able to compute f(x) based on x′. In this paper we study the existence of functions which are incompressible by circuits of some fixed polynomial size \({s=n^c}\). Motivated by cryptographic applications, we focus on average-case \({(\ell,\epsilon)}\) incompressibility, which guarantees that on a random input \({x\in \{0,1\}^n}\), for every size s circuit \({C:\{0,1\}^n\rightarrow \{0,1\}^{\ell}}\) and any unbounded solver D, the success probability \({\Pr_x[D(C(x))=f(x)]}\) is upper-bounded by \({2^{-m}+\epsilon}\). While this notion of incompressibility appeared in several works (e.g., Dubrov and Ishai, STOC 06), so far no explicit constructions of efficiently computable incompressible functions were known. In this work, we present the following results:

1. (1)
   Assuming that E is hard for exponential size nondeterministic circuits, we construct a polynomial time computable boolean function \({f:\{0,1\}^n\rightarrow \{0,1\}}\) which is incompressible by size n ^c circuits with communication \({\ell=(1-o(1)) \cdot n}\) and error \({\epsilon=n^{-c}}\). Our technique generalizes to the case of PRGs against nonboolean circuits, improving and simplifying the previous construction of Shaltiel and Artemenko (STOC 14).
    
2. (2)
   We show that it is possible to achieve negligible error parameter \({\epsilon=n^{-\omega(1)}}\) for nonboolean functions. Specifically, assuming that E is hard for exponential size \({\Sigma_3}\)-circuits, we construct a nonboolean function \({f:\{0,1\}^n\rightarrow \{0,1\}^m}\) which is incompressible by size n ^c circuits with \({\ell=\Omega(n)}\) and extremely small \({\epsilon=n^{-c} \cdot 2^{-m}}\). Our construction combines the techniques of Trevisan and Vadhan (FOCS 00) with a new notion of relative error deterministic extractor which may be of independent interest.
    
3. (3)
   We show that the task of constructing an incompressible boolean function \({f:\{0,1\}^n\rightarrow \{0,1\}}\) with negligible error parameter \({\epsilon}\) cannot be achieved by “existing proof techniques”. Namely, nondeterministic reductions (or even \({\Sigma_i}\) reductions) cannot get \({\epsilon=n^{-\omega(1)}}\) for boolean incompressible functions. Our results also apply to constructions of standard Nisan-Wigderson type PRGs and (standard) boolean functions that are hard on average, explaining, in retrospect, the limitations of existing constructions. Our impossibility result builds on an approach of Shaltiel and Viola (STOC 08).
    

     

The Complexity of König Subgraph Problems and Above-Guarantee Vertex Cover

A graph is König-Egerváry if the size of a minimum vertex cover equals that of a maximum matching in the graph. These graphs have been studied extensively from a graph-theoretic point of view. In this paper, we introduce and study the algorithmic complexity of finding König-Egerváry subgraphs of a given graph. In particular, given a graph G and a nonnegative integer k, we are interested in the following questions:

1. 1.
   does there exist a set of k vertices (edges) whose deletion makes the graph König-Egerváry?
    
2. 2.
   does there exist a set of k vertices (edges) that induce a König-Egerváry subgraph?
    

We show that these problems are NP-complete and study their complexity from the points of view of approximation and parameterized complexity. Towards this end, we first study the algorithmic complexity of Above Guarantee Vertex Cover, where one is interested in minimizing the additional number of vertices needed beyond the maximum matching size for the vertex cover. Further, while studying the parameterized complexity of the problem of deleting k vertices to obtain a König-Egerváry graph, we show a number of interesting structural results on matchings and vertex covers which could be useful in other contexts.