Browsing by Subject "Computational complexity"
Now showing items 120 of 152

2D Tucker is PPA complete
(202003)
Article
Open AccessThe 2D Tucker search problem is shown to be PPAhard under manyone reductions; therefore it is complete for PPA. The same holds for kD Tucker for all k≥2. This corrects a claim in the literature that the Tucker search ... 
A biased random key genetic algorithm for the weighted independent domination problem
(Association for Computing Machinery (ACM), 2019)
Conference lecture
Open AccessThis work deals with an NPhard problem in graphs known as the weighted independent domination problem. We propose a biased random key genetic algorithm for solving this problem. The most important part of the proposed ... 
A block algorithm for the algebraic path problem and its execution on a systolic array
(Institute of Electrical and Electronics Engineers (IEEE), 1989)
Conference report
Open AccessThe solution of the algebraic path problem (APP) for arbitrarily sized graphs by a fixedsize systolic array processor (SAP) is addressed. The APP is decomposed into two subproblems, and SAP is designed for each one. Both ... 
A case for merging the ILP and DLP paradigms
(Institute of Electrical and Electronics Engineers (IEEE), 1998)
Conference report
Open AccessThe goal of this paper is to show that instruction level parallelism (ILP) and datalevel parallelism (DLP) can be merged in a single architecture to execute vectorizable code at a performance level that can not be achieved ... 
A combinatorial technique for separating counting complexity classes
(1988)
External research report
Open AccessWe introduce a new combinatorial technique to obtain relativized separations of certain complexity classes related to the idea of counting, like PP, G (exact counting), and ¿P (parity). To demonstrate its usefulness we ... 
A fast OFDMCDMA user demultiplexing architecture
(Institute of Electrical and Electronics Engineers (IEEE), 2000)
Conference report
Open AccessA fast algorithm based on a butterfly structure is presented that demultiplexes the symbols of a particular type of MCMA (multicarrier multipleaccess) modulation previously proposed for indoor radio communications. A ... 
A logic programming approach to parsing and production in fluid construction grammar
(Springer, 2012)
Part of book or chapter of book
Restricted access  publisher's policyThis paper presents a Logic Programming approach to parsing and production in Fluid Construction Grammar (FCG). It builds on previous work on the formalisation of FCG in terms of First Order Logic (FOL) concepts, more ... 
A mathematical formulation of the loop pipelining problem
(Universitat Politècnica de Catalunya (UPC), 1996)
Conference report
Open AccessThis paper presents a mathematical model for the loop pipelining problem that considers several parameters for optimization and supports any combination of resource and timing constraints. The unrolling degree of the loop ... 
A parameterized halting problem, the linear time hierarchy, and the MRDP theorem
(Association for Computing Machinery (ACM), 2018)
Conference report
Open AccessThe complexity of the parameterized halting problem for nondeterministic Turing machines pHalt is known to be related to the question of whether there are logics capturing various complexity classes [10]. Among others, ... 
A performance characterization of high definition digital video decoding using H.264/AVC
(Institute of Electrical and Electronics Engineers (IEEE), 2005)
Conference report
Open AccessH.264/AVC is a new international video coding standard that provides higher coding efficiency with respect to previous standards at the expense of a higher computational complexity. The complexity is even higher when ... 
A positive relativization of polynomial time vs. polylog space
(199105)
External research report
Open AccessCan every set in P be solved in polylogarithmic space? We show that this question is equivalent to asking whether the classes PSPACE and EXPTIME are always equal under relativization. We use an oracle access mechanism that ... 
A reducedcomplexity and asymptotically efficient timedelay estimator
(ICASSP, 2000)
Conference report
Open AccessThis paper considers the problem of estimating the time delays of multiple replicas of a known signal received by an array of antennas. Under the assumptions that the noise and cochannel interference (CCI) are spatially ... 
A study of the humansystem interface complexity sources in wastewater treatment plants
(Universidad de Zaragoza, 2012)
Conference report
Restricted access  publisher's policyIn humanautomation interaction it is necessary to define methods and tools to assess the humansystem interface complexity. In a first assessment, the use of an evaluation questionnaire aiming at detecting complexity ... 
Acceleration of Born series by change of variables
(202109)
Article
Open AccessIn this work, we propose a method to enhance the convergence of the Born series. The Born series is widely used in scattering theory, but its convergence is only guaranteed under certain restrictive conditions which limit ... 
Adaptive logspace and depthbounded reducibilities
(199104)
External research report
Open AccessWe discuss a number of results regarding an important subject: the study of the computational power of depthbounded reducibilities, their use to classify the complexity of computational problems, and their characterizations ... 
Adaptive logspace reducibility and parallel time
(199111)
External research report
Open AccessWe discuss two notions of functional oracle for logarithmic spacebounded machines, which differ in whether there is only one oracle tape for both the query and the answer or a separate tape for the answer, which can still ... 
Algorismes parametritzats per al problema de recobriment d'imatges
(Universitat Politècnica de Catalunya, 20070114)
Master thesis (preBologna period)
Open Access 
Aligning modeled and observed behavior: A compromise between computation complexity and quality
(Springer, 2017)
Conference report
Open AccessCertifying that a process model is aligned with the real process executions is perhaps the most desired feature a process model may have: aligned process models are crucial for organizations, since strategic decisions can ... 
Almost every set in exponential time is PBiImmune
(19911106)
External research report
Open AccessA set A is Pbiimmune if neither A nor its complement has an infinite subset in P. We investigate here the abundance of Pbiimmune languages in linearexponential time (E). We prove that the class of Pbiimmune sets ... 
An efficient solver for Cache Miss Equations
(Institute of Electrical and Electronics Engineers (IEEE), 2000)
Conference report
Open AccessCache Miss Equations (CME) (S. Ghosh et al., 1997) is a method that accurately describes the cache behavior by means of polyhedra. Even though the computation cost of generating CME is a linear function of the number of ...