Hardness Hypotheses, Derandomization, and Circuit Complexity

We consider hypotheses about nondeterministic computation that have been studied in different contexts and shown to have interesting consequences:

Inverse NP Problems

The inverse problem relative to a verifier V of proofs of membership for a NP language is the problem of deciding, given a set π of proofs, whether or not there exists a string x having exactly π as its set of proofs. In this paper, we study the complexity of inverse problems. We develop a new notion of reduction which allows one to compare the complexity of inverse problems. Using this notion, we classify as coNP-complete the inverse problems for the “natural” verifiers of many NP-complete problems. We also show that the inverse complexity of a verifier for a language L cannot be predicted solely from the complexity of L, but rather, is highly dependent upon the choice of verifier used to accept L. In this context, a verifier with a Σ₂ ^p -complete inverse problem is exhibited, giving a new and natural example of a Σ₂ ^p -complete problem.      

Randomness-Efficient Sampling within NC1

We construct a randomness-efficient averaging sampler that is computable by uniform constant-depth circuits with parity gates (i.e., in uniform AC ⁰[⊕]). Our sampler matches the parameters achieved by random walks on constant-degree expander graphs, allowing us to apply a variety expander-based techniques within NC ¹. For example, we obtain the following results:

Direct links in IEEE 802.11: Analytical study of unfairness problem

In this paper, the problem of mutual interference between direct links in IEEE 802.11 networks is represented. This problem is common for direct links in infrastructure networks with hidden terminals and for mesh networks as well. In this paper, we develop analytical models to study the impact of the direct link interference on links performance indices in various cases of links disposition. With these models proved by simulation, we show that network capacity distribution between direct links is unfair in many cases, explaining the reasons of the unfairness in every case. As a conclusion, we discuss possible mechanisms to solve the unfairness problem.     

Perfect Parallel Repetition Theorem for Quantum Xor Proof Systems

We consider a class of two-prover interactive proof systems where each prover returns a single bit to the verifier and the verifier’s verdict is a function of the XOR of the two bits received. We show that, when the provers are allowed to coordinate their behavior using a shared entangled quantum state, a perfect parallel repetition theorem holds in the following sense. The prover’s optimal success probability for simultaneously playing a collection of XOR proof systems is exactly the product of the individual optimal success probabilities. This property is remarkable in view of the fact that, in the classical case (where the provers can only utilize classical information), it does not hold. The theorem is proved by analyzing parities of XOR proof systems using semidefinite programming techniques, which we then relate to parallel repetitions of XOR games via Fourier analysis.      

Gaining insight through case-based explanation

Traditional explanation strategies in machine learning have been dominated by rule and decision tree based approaches. Case-based explanations represent an alternative approach which has inherent advantages in terms of transparency and user acceptability. Case-based explanations are based on a strategy of presenting similar past examples in support of and as justification for recommendations made. The traditional approach to such explanations, of simply supplying the nearest neighbour as an explanation, has been found to have shortcomings. Cases should be selected based on their utility in forming useful explanations. However, the relevance of the explanation case may not be clear to the end user as it is retrieved using domain knowledge which they themselves may not have. In this paper the focus is on a knowledge-light approach to case-based explanations that works by selecting cases based on explanation utility and offering insights into the effects of feature-value differences. In this paper we examine to two such a knowledge-light frameworks for case-based explanation. We look at explanation oriented retrieval (EOR) a strategy which explicitly models explanation utility and also at the knowledge-light explanation framework (KLEF) that uses local logistic regression to support case-based explanation.

Space Complexity Vs. Query Complexity

Combinatorial property testing deals with the following relaxation of decision problems: Given a fixed property and an input x, one wants to decide whether x satisfies the property or is “far” from satisfying it. The main focus of property testing is in identifying large families of properties that can be tested with a certain number of queries to the input. In this paper we study the relation between the space complexity of a language and its query complexity. Our main result is that for any space complexity s(n) ≤ log n there is a language with space complexity O(s(n)) and query complexity 2^Ω(s(n)). Our result has implications with respect to testing languages accepted by certain restricted machines. Alon et al. [FOCS 1999] have shown that any regular language is testable with a constant number of queries. It is well known that any language in space o(log log n) is regular, thus implying that such languages can be so tested. It was previously known that there are languages in space O(log n) that are not testable with a constant number of queries and Newman [FOCS 2000] raised the question of closing the exponential gap between these two results. A special case of our main result resolves this problem as it implies that there is a language in space O(log log n) that is not testable with a constant number of queries. It was also previously known that the class of testable properties cannot be extended to all context-free languages. We further show that one cannot even extend the family of testable languages to the class of languages accepted by single counter machines.      

Fuzzy logic deduction with crisp observations

This paper presents an approach to approximate reasoning over a set of IF-THEN rules called fuzzy logic deduction. It understands IF-THEN rules as linguistically expressed logical implications and interprets them inside formal logical theory. Methodology and some properties are presented. This paper has been supported by the Grant A1187901/99 of the GA AV R and project W-00-016 of the Cz-US scientific cooperation.     

Modeling and Processing Information for Context-Aware Computing: A Survey

Context-awareness is emerging as a central issue in ubiquitous computing research. Context-aware computing refers to the idea that computing devices can sense and react to the physical environment where they are deployed. A great deal of research on context-awareness has been conducted to explore and address the various challenges related to context acquisition, representation, distribution, and abstraction. This paper surveys the most relevant approaches to modeling context for ubiquitous computing. It also evaluates how the existing works utilize contextual information, with respect to the query processing approaches used to access and manage that information. We also discuss typical problems, shortcomings, and challenges posed by context modeling at large, and highlight some proposals to address some of them.